标题： 密集和稀疏对称矩阵在任意域上的快速LDL分解 显示英文标题

标题： Fast LDL factorization for dense and sparse symmetric matrices over an arbitrary field

摘要： 虽然现有的算法可能用于在矩阵乘法时间内求解一般域上的线性系统，但构造对称三角分解（LDL）的复杂性却相对较少被正式研究。 LDL分解是用于对称矩阵分解的常用工具，与正交方法不同，它可推广到任意域。 我们提供了用于密集和稀疏LDL和LU分解的算法，旨在最小化在一般域上分解的复杂性。 对于$n\times n$矩阵的LDL分解，我们给出一个复杂度为$O(n^\omega)$的算法，其中假设$n\times n$矩阵乘法的复杂度为$O(n^\omega)$，其中$\omega>2$。 对于对应于具有分支宽度$\tau$的图的稀疏矩阵，我们给出一个复杂度为$O(n\tau^{\omega-1})$的算法，以计算隐式形式的LDL，或者如果矩阵接近满秩，则计算显式的LDL。 我们的稀疏LDL算法基于对求解鞍点方程组的零空间方法的适应，这可能有独立的兴趣。 稀疏LDL分解算法还可扩展为计算稀疏LU分解。 显示英文摘要

摘要： While existing algorithms may be used to solve a linear system over a general field in matrix-multiplication time, the complexity of constructing a symmetric triangular factorization (LDL) has received relatively little formal study. The LDL factorization is a common tool for factorization of symmetric matrices, and, unlike orthogonal counterparts, generalizes to an arbitrary field. We provide algorithms for dense and sparse LDL and LU factorization that aim to minimize complexity for factorization over a general field. For LDL of an $n\times n$ matrix, we give an algorithm with complexity $O(n^\omega)$, where the complexity of $n\times n$ matrix multiplication is assumed to be $O(n^\omega)$ with $\omega>2$. For sparse matrices corresponding to graphs with treewidth $\tau$, we give an algorithm with complexity $O(n\tau^{\omega-1})$, to compute an LDL an implicit form, or the explicit LDL if the matrix is near full rank. Our sparse LDL algorithm is based on an adaptation of the null-space method for solving saddle point systems of equations, which may be of independent interest. The sparse LDL factorization algorithm also extends to computing a sparse LU factorization.