线性⽅程组直接解法相关论⽂研读
线性⽅程组直接解法相关论⽂研读
A survey of direct methods for sparse linear systems
介绍
GPU-accelerated Multifrontal methods
总结
GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis
介绍
Left-looking
Right-looking
实验
Using dense storage to solve sparse linear system
摘要
介绍
Cholesky 分解相关论⽂研究
稀疏矩阵 Cholesky 分解法
数据组织
任务⽣成与调度⽅法
实验结果
总结与下⼀步的计划
A survey of direct methods for sparse linear
systems
介绍
这篇综述由德州农⼯⼤学完成,它总结了稀疏矩阵直接解法的基本原理,涵盖了LU、QR、Cholesky和
其他因⼦分解、正/反解以及相关的矩阵运算。它深⼊介绍了可⽤于解决稀疏矩阵问题的许多算法和软
件,包括串⾏和并⾏算法。
本⽂的前⼗⼀节介绍了稀疏矩阵求解的数据结构、求解过程以及各种求解⽅法;⽽在第⼗⼆节中讨论了
⼀些进阶的内容,其中就包括了GPU并⾏加速的⼀些研究成果。
GPU-accelerated Multifrontal methods
近年来,针对稀疏矩阵的并⾏加速算法都是针对Frontal solver进⾏优化,采⽤⼀种被⼴泛使⽤的稀疏矩
阵分解⽅法——Multifrontal⽅法。Multifrontal⽅法来源于⾼斯消元在有限元中的应⽤,具体的算法
可以参考这篇⽂章。从⾼性能计算的⻆度来看,组装树中没有依赖的分⽀可以进⾏并⾏计算;此外,每
个结点上的计算都是稠密矩阵计算,可以采⽤⾼度优化的稠密矩阵运算库进⾏计算。
本⽂介绍了从2009年到2016年相关算法的优化过程:
1. 2009 年 Pierce 等⼈在做 multifrontal Cholesky 分解时,将⼀个⼤的 frontal 矩阵传到 GPU 进⾏