Numerical Linear Algebra in Linear Space
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909674696081408 |
|---|---|
| author | Liu, Yiping Nguyen, Hoai-An Yang, Junzhao |
| author_facet | Liu, Yiping Nguyen, Hoai-An Yang, Junzhao |
| contents | We present a randomized linear-space solver for general linear systems $\mathbf{A} \mathbf{x} = \mathbf{b}$ with $\mathbf{A} \in \mathbb{Z}^{n \times n}$ and $\mathbf{b} \in \mathbb{Z}^n$, without any assumption on the condition number of $\mathbf{A}$. For matrices whose entries are bounded by $\mathrm{poly}(n)$, the solver returns a $(1+ε)$-multiplicative entry-wise approximation to vector $\mathbf{x} \in \mathbb{Q}^{n}$ using $\widetilde{O}(n^2 \cdot \mathrm{nnz}(\mathbf{A}))$ bit operations and $O(n \log n)$ bits of working space (i.e., linear in the size of a vector), where $\mathrm{nnz}$ denotes the number of nonzero entries. Our solver works for right-hand vector $\mathbf{b}$ with entries up to $n^{O(n)}$. To our knowledge, this is the first linear-space linear system solver over the rationals that runs in $\widetilde{O}(n^2 \cdot \mathrm{nnz}(\mathbf{A}))$ time.
We also present several applications of our solver to numerical linear algebra problems, for which we provide algorithms with efficient polynomial running time and near-linear space. In particular, we present results for linear regression, linear programming, eigenvalues and eigenvectors, and singular value decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02433 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Numerical Linear Algebra in Linear Space Liu, Yiping Nguyen, Hoai-An Yang, Junzhao Data Structures and Algorithms We present a randomized linear-space solver for general linear systems $\mathbf{A} \mathbf{x} = \mathbf{b}$ with $\mathbf{A} \in \mathbb{Z}^{n \times n}$ and $\mathbf{b} \in \mathbb{Z}^n$, without any assumption on the condition number of $\mathbf{A}$. For matrices whose entries are bounded by $\mathrm{poly}(n)$, the solver returns a $(1+ε)$-multiplicative entry-wise approximation to vector $\mathbf{x} \in \mathbb{Q}^{n}$ using $\widetilde{O}(n^2 \cdot \mathrm{nnz}(\mathbf{A}))$ bit operations and $O(n \log n)$ bits of working space (i.e., linear in the size of a vector), where $\mathrm{nnz}$ denotes the number of nonzero entries. Our solver works for right-hand vector $\mathbf{b}$ with entries up to $n^{O(n)}$. To our knowledge, this is the first linear-space linear system solver over the rationals that runs in $\widetilde{O}(n^2 \cdot \mathrm{nnz}(\mathbf{A}))$ time. We also present several applications of our solver to numerical linear algebra problems, for which we provide algorithms with efficient polynomial running time and near-linear space. In particular, we present results for linear regression, linear programming, eigenvalues and eigenvectors, and singular value decomposition. |
| title | Numerical Linear Algebra in Linear Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.02433 |