Sparsified Cholesky and multigrid solvers for connection laplacians
Sparsified Cholesky and multigrid solvers for connection laplacians
复制标题
用于连接拉普拉斯的稀疏 Cholesky 和多重网格求解器
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Spielman
中科院分区：
文献类型：
--
作者：
Rasmus Kyng;Y. Lee;Richard Peng;Sushant Sachdeva;D. Spielman
我们介绍了稀疏Cholesky和稀疏多重网格算法求解线性方程组。这些算法通过稀疏化由消除过程创建的非零矩阵项来加速高斯消除。我们使用这些新的算法，以获得第一个近线性时间算法求解方程组的连接Laplacian-在图像和信号处理中出现的许多问题的Laplacian矩阵的推广。我们还证明了每个连接拉普拉斯算子都有一个线性大小的近似逆。这是一个LU分解，具有线性数量的非零元素，是原始矩阵的强近似。使用这样的因式分解，可以在线性时间内求解连接拉普拉斯算子中的方程组。这样的因式分解是未知的，即使是普通的图形拉普拉斯。
We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians---a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the original matrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.