Method for Verifying Solutions of Sparse Linear Systems with General Coefficients
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909216031113216 |
|---|---|
| author | Terao, Takeshi Ozaki, Katsuhisa |
| author_facet | Terao, Takeshi Ozaki, Katsuhisa |
| contents | This paper proposes a verification method for sparse linear systems $Ax=b$ with general and nonsingular coefficients. A verification method produces the error bound for a given approximate solution. Conventional methods use one of two approaches. One approach is to verify the computed solution of the normal equation $A^TAx=A^Tb$ by exploiting symmetric and positive definiteness; however, the condition number of $A^TA$ is the square of that for $A$. The other approach uses an approximate inverse matrix of the coefficient; however, the approximate inverse may be dense even if $A$ is sparse. Here, we propose a method for the verification of solutions of sparse linear systems based on $LDL^T$ decomposition. The proposed method can reduce the fill-in and is applicable to many problems. Moreover, an efficient iterative refinement method is proposed for obtaining accurate solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_02033 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Method for Verifying Solutions of Sparse Linear Systems with General Coefficients Terao, Takeshi Ozaki, Katsuhisa Numerical Analysis 65G20, 65F50, 65F05 This paper proposes a verification method for sparse linear systems $Ax=b$ with general and nonsingular coefficients. A verification method produces the error bound for a given approximate solution. Conventional methods use one of two approaches. One approach is to verify the computed solution of the normal equation $A^TAx=A^Tb$ by exploiting symmetric and positive definiteness; however, the condition number of $A^TA$ is the square of that for $A$. The other approach uses an approximate inverse matrix of the coefficient; however, the approximate inverse may be dense even if $A$ is sparse. Here, we propose a method for the verification of solutions of sparse linear systems based on $LDL^T$ decomposition. The proposed method can reduce the fill-in and is applicable to many problems. Moreover, an efficient iterative refinement method is proposed for obtaining accurate solutions. |
| title | Method for Verifying Solutions of Sparse Linear Systems with General Coefficients |
| topic | Numerical Analysis 65G20, 65F50, 65F05 |
| url | https://arxiv.org/abs/2406.02033 |