A Family of Iteration Functions for General Linear Systems

Bahman Kalantari

RECORD

A Family of Iteration Functions for General Linear Systems

Bahman Kalantari

Numerical Analysis · Submitted 11 Apr 2023

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim The results support CTA as a highly competitive option.

how it is stated · asserted 0.84 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 10,744 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.15 · human participants 0.01 · controlled comparison 0.51 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.94 · mentions code or data availability 0.03.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

We introduce innovative algorithms for computing exact or approximate (minimum-norm) solutions to $Ax=b$ or the {\it normal equation} $A^TAx=A^Tb$, where $A$ is an $m \times n$ real matrix of arbitrary rank. We present more efficient algorithms when $A$ is symmetric PSD. First, we introduce the {\it Triangle Algorithm} (TA), a {\it convex-hull membership} algorithm that given $b_k=Ax_k$ in the ellipsoid $E_{A,\rho}=\{Ax: \Vert x \Vert \leq \rho\}$, it either computes an improved approximation $b_{k+1}=Ax_{k+1}$ or proves $b \not \in E_{A,\rho}$. We then give a dynamic variant of TA, the {\it Centering Triangle Algorithm} (CTA), generating residual, $r_k=b -Ax_k$ via the iteration of $F_1(r)=r-(r^THr/r^TH^2r)Hr$, where $H=AA^T$. If $A$ is symmetric PSD, $H$ can be taken as $A$. Next, for each $t=1, \dots, m$, we derive $F_t(r)=r- \sum_{i=1}^t \alpha_{t,i}(r) H^i r$ whose iterations correspond to a Krylov subspace method with restart. If $\kappa^+(H)$ is the ratio of the largest to smallest positive eigenvalues of $H$, when $Ax=b$ is consistent, in $k=O({\kappa^+(H)}{t^{-1}} \ln \varepsilon^{-1})$ iterations of $F_t$, $\Vert r_k \Vert \leq \varepsilon$. Each iteration takes $O(tN+t^3)$ operations, $N$ the number of nonzero entries in $A$. By directly applying $F_t$ to the normal equation, we get $\Vert A^TAx_k - A^Tb \Vert \leq \varepsilon$ in $O({\kappa^+(AA^T)}{t}^{-1} \ln \varepsilon^{-1})$ iterations. On the other hand, given any residual $r$, we compute $s$, the degree of its minimal polynomial with respect to $H$ in $O(sN+s^3)$ operations. Then $F_s(r)$ gives the minimum-norm solution of $Ax=b$ or an exact solution of $A^TAx=A^Tb$. The proposed algorithms are simple to implementation and theoretically robust. We present sample computational results, comparing the performance of CTA with CG and GMRES methods. The results support CTA as a highly competitive option.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We introduce innovative algorithms for computing exact or approximate (minimum-norm) solutions to $Ax=b$ or the {\it normal equation} $A^TAx=A^Tb$, where $A$ is an $m \times n$ real matrix of arbitrary rank.	contribution 1.00	0.93	0.20	asserted 1.00
s1	We present more efficient algorithms when $A$ is symmetric PSD.	contribution 1.00	0.88	0.05	asserted 1.00
s2	First, we introduce the {\it Triangle Algorithm} (TA), a {\it convex-hull membership} algorithm that given $b_k=Ax_k$ in the ellipsoid $E_{A,\rho}=\{Ax: \Vert x \Vert \leq \rho\}$, it either computes an improved approximation $b_{k+1}=Ax_{k+1}$ or proves $b \not \in E_{A,\rho}$.	contribution 0.52	0.91	0.06	asserted 1.00
s3	We then give a dynamic variant of TA, the {\it Centering Triangle Algorithm} (CTA), generating residual, $r_k=b -Ax_k$ via the iteration of $F_1(r)=r-(r^THr/r^TH^2r)Hr$, where $H=AA^T$.	method 0.62	0.95	0.05	asserted 1.00
s4	If $A$ is symmetric PSD, $H$ can be taken as $A$.	method 0.90	0.51	0.02	asserted 0.69
s5	Next, for each $t=1, \dots, m$, we derive $F_t(r)=r- \sum_{i=1}^t \alpha_{t,i}(r) H^i r$ whose iterations correspond to a Krylov subspace method with restart.	method 0.65	0.95	0.04	asserted 1.00
s6	If $\kappa^+(H)$ is the ratio of the largest to smallest positive eigenvalues of $H$, when $Ax=b$ is consistent, in $k=O({\kappa^+(H)}{t^{-1}} \ln \varepsilon^{-1})$ iterations of $F_t$, $\Vert r_k \Vert \leq \varepsilon$.	result 0.96	0.87	0.13	asserted 1.00
s7	Each iteration takes $O(tN+t^3)$ operations, $N$ the number of nonzero entries in $A$.	result 0.60	0.85	0.03	asserted 1.00
s8	By directly applying $F_t$ to the normal equation, we get $\Vert A^TAx_k - A^Tb \Vert \leq \varepsilon$ in $O({\kappa^+(AA^T)}{t}^{-1} \ln \varepsilon^{-1})$ iterations.	result 0.89	0.89	0.10	asserted 1.00
s9	On the other hand, given any residual $r$, we compute $s$, the degree of its minimal polynomial with respect to $H$ in $O(sN+s^3)$ operations.	method 0.83	0.88	0.04	asserted 1.00
s10	Then $F_s(r)$ gives the minimum-norm solution of $Ax=b$ or an exact solution of $A^TAx=A^Tb$.	result 0.56	0.88	0.17	asserted 1.00
s11	The proposed algorithms are simple to implementation and theoretically robust.	interpretation 0.80	0.43	0.15	asserted 1.00
s12	We present sample computational results, comparing the performance of CTA with CG and GMRES methods.	contribution 0.52	0.95	0.05	asserted 0.94
s13	The results support CTA as a highly competitive option.	interpretation 0.88	0.90	0.51	asserted 0.84

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from proof or derivation 0.92.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

We introduce innovative algorithms for computing exact or approximate (minimum-norm) solutions to $Ax=b$ or the {\it normal equation} $A^TAx=A^Tb$, where $A$ is an $m \times n$ real matrix of arbitrary rank. We present more efficient algorithms when $A$ is symmetric PSD. First, we introduce the {\it Triangle Algorithm} (TA), a {\it convex-hull membership} algorithm that given $b_k=Ax_k$ in the ellipsoid $E_{A,\rho}=\{Ax: \Vert x \Vert \leq \rho\}$, it either computes an improved approximation $b_{k+1}=Ax_{k+1}$ or proves $b \not \in E_{A,\rho}$. We then give a dynamic variant of TA, the {\it Centering Triangle Algorithm} (CTA), generating residual, $r_k=b -Ax_k$ via the iteration of $F_1(r)=r-(r^THr/r^TH^2r)Hr$, where $H=AA^T$. If $A$ is symmetric PSD, $H$ can be taken as $A$. Next, for each $t=1, \dots, m$, we derive $F_t(r)=r- \sum_{i=1}^t \alpha_{t,i}(r) H^i r$ whose iterations correspond to a Krylov subspace method with restart. If $\kappa^+(H)$ is the ratio of the largest to smallest positive eigenvalues of $H$, when $Ax=b$ is consistent, in $k=O({\kappa^+(H)}{t^{-1}} \ln \varepsilon^{-1})$ iterations of $F_t$, $\Vert r_k \Vert \leq \varepsilon$. Each iteration takes $O(tN+t^3)$ operations, $N$ the number of nonzero entries in $A$. By directly applying $F_t$ to the normal equation, we get $\Vert A^TAx_k - A^Tb \Vert \leq \varepsilon$ in $O({\kappa^+(AA^T)}{t}^{-1} \ln \varepsilon^{-1})$ iterations. On the other hand, given any residual $r$, we compute $s$, the degree of its minimal polynomial with respect to $H$ in $O(sN+s^3)$ operations. Then $F_s(r)$ gives the minimum-norm solution of $Ax=b$ or an exact solution of $A^TAx=A^Tb$. The proposed algorithms are simple to implementation and theoretically robust. We present sample computational results, comparing the performance of CTA with CG and GMRES methods. The results support CTA as a highly competitive option.

Human review

How Pith checks papers → · Full audit of this paper →

How the literature uses it

1 arXiv paper cite this in 16 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 12 sentences without a confident label

Uses its method or tool 1 paper

In this article we consider the computational performance of a class of iterative methods, developed by Kalantari [ref] , intended to solve either the linear system $Ax=b$ or the normal equation $A^TAx=A^Tb$, where $A$ is an $m ×n$ real matrix of arbitrary rank.

On the Performance of a Novel Class of Linear System Solvers and Comparison with State-of-The-Art Algorithms · Introduction · 0.85

Cites it as background 1 paper

Here we give relevant definitions used in [ref] and in the computations to be presented in this article.

On the Performance of a Novel Class of Linear System Solvers and Comparison with State-of-The-Art Algorithms · Definition of Approximation Solutions · 0.92

What it cites · 4 sentences without a confident label

Uses the method or tool of 1 paper

They can accomplish this by conducting experiments with their unique linear systems, utilizing either the implementations of CTA or TA as detailed in [ref] , or by creating their own versions of these algorithms.

On the Performance of a Novel Class of Linear System Solvers and Comparison with State-of-The-Art Algorithms · Final Remarks · 0.93

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.