The double splitting iteration method for solving the large indefinite least squares problem

Technical Summary: The Double Splitting Iteration Method for Large Indefinite Least Squares Problems

Problem Statement
The paper addresses the computational challenges associated with solving large-scale indefinite least squares (ILS) problems, formulated as minimizing the indefinite quadratic form $(b - Ax)^T J (b - Ax)$, where $A \in \mathbb{R}^{m \times n}$ is a large sparse matrix, $b \in \mathbb{R}^m$, and $J = \text{diag}(I_p, -I_q)$ is a signature matrix with $p+q=m$. When $pq > 0$, the problem leads to a normal equation $A^T J A x = A^T J b$ involving a Hessian matrix that is not positive definite. While direct methods exist for small dense problems, iterative schemes are preferred for large-scale systems. Existing state-of-the-art iterative solvers for this problem predominantly rely on single splitting strategies of the coefficient matrix $A^T J A = M - N$, such as the Splitting-based (SP), Generalized SP (GSP), and Alternating Direction Implicit (ADI) methods.

Methodology
The authors propose a novel Double Splitting (DS) iteration method. Unlike traditional approaches that decompose the coefficient matrix into two parts ($M - N$), this method utilizes a three-part decomposition:
$$A^T J A = P - R - S$$
where $P$ is a nonsingular matrix. Inspired by the structure of the GSP method, the authors define specific matrices based on the partition $A = [A_1; A_2]$:

• $P = \alpha I + A_1^T A_1$ (Symmetric Positive Definite, SPD)
• $R = A_2^T A_2$ (Symmetric)
• $S = \alpha I$ (Symmetric)
  where $\alpha > 0$ is a given parameter.

This decomposition leads to a two-step stationary iteration scheme:
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
This formulation incorporates information from the two previous iterates ($x_k$ and $x_{k-1}$), distinguishing it from the one-step nature of SP and GSP methods. The convergence of this scheme is analyzed by examining the spectral radius $\rho(W)$ of the associated block iteration matrix $W$. The authors derive a scalar quadratic equation for the eigenvalues $\lambda$ of $W$ and apply a lemma regarding the roots of quadratic equations to prove that $|\lambda| < 1$ for all $\alpha > 0$.

Key Contributions

1. Novel Iterative Framework: The paper introduces a concrete double splitting strategy tailored specifically for the normal equations arising from ILS problems, offering a distinct alternative to the dominant single splitting paradigms.
2. Unconditional Convergence Proof: The authors provide a rigorous spectral analysis demonstrating that the proposed DS iteration method converges unconditionally for any positive parameter $\alpha$. This result is further contextualized by connecting it to existing convergence criteria for Hermitian positive definite matrices found in prior literature.
3. Algorithmic Implementation: A detailed algorithm (Algorithm 2.1) is presented, outlining the computational steps, including the use of Cholesky decomposition for inverting the SPD matrix $P$.

Numerical Results
Two numerical experiments were conducted to evaluate the performance of the DS method against the SP, GSP, and ADI methods:

• Example 3.1 (Dense Matrices): Using random large-scale dense matrices, the DS method was tested with varying dimensions ($m$ up to 54,000). With an optimal parameter $\alpha=1$, the DS method converged in exactly 2 iterations. While SP and GSP also converged in 1 iteration, the DS method achieved significantly lower CPU times (e.g., ~4.8s vs. ~75s for GSP at $m=51,000$).
• Example 3.2 (Sparse Matrices): Using matrices derived from total least squares problems, the DS method was tested with sparse structures. With an optimal parameter $\alpha=10^{-4}$, the DS method again converged in 2 iterations. It consistently outperformed the single splitting methods in computational time across all tested sizes (up to $m=8,192$), demonstrating superior efficiency even as problem size increased.

Significance and Claims
The paper claims that the proposed double splitting iteration paradigm offers a constructive improvement over conventional single splitting approaches. The primary significance lies in the method's ability to achieve faster convergence speed (in terms of CPU time) and robustness for large-scale ILS problems. The authors emphasize that while the method requires two previous iterates, the incorporation of this historical information allows for a substantial reduction in computational cost compared to the single-step SP, GSP, and ADI methods. The work provides methodological references for future research into double splitting-based iterative methods and suggests potential extensions to adaptive parameter selection and other types of indefinite linear systems.