标题： 任意域上稠密和稀疏对称矩阵的快速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 nd 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.