Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2504.20305 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912448547651584 |
|---|---|
| author | Solomonik, Edgar |
| author_facet | Solomonik, Edgar |
| contents | 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^ω)$, where the complexity of $n\times n$ matrix multiplication is assumed to be $O(n^ω)$ with $ω>2$. For sparse matrices corresponding to graphs with treewidth $τ$, we give an algorithm with complexity $O(nτ^{ω-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast LDL factorization for dense and sparse symmetric matrices over an arbitrary field Solomonik, Edgar Numerical Analysis 15-02, 65Yxx, 68Qxx 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^ω)$, where the complexity of $n\times n$ matrix multiplication is assumed to be $O(n^ω)$ with $ω>2$. For sparse matrices corresponding to graphs with treewidth $τ$, we give an algorithm with complexity $O(nτ^{ω-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. |
| title | Fast LDL factorization for dense and sparse symmetric matrices over an arbitrary field |
| topic | Numerical Analysis 15-02, 65Yxx, 68Qxx |
| url | https://arxiv.org/abs/2504.20305 |