Source-linked AI summary
Solving Large-Scale Sparse Linear Complementarity Problems Using a Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method
Abhishek Kumar Singh Sengar, Bharat Kumar, Deepmala
TL;DR
Large-scale sparse LCP solvers must preserve exploitable matrix structure while achieving efficient convergence. The paper introduces a relaxed shifted modulus-based splitting framework with two tunable shifts, and experiments show competitive performance across four sparse problems, including a quasi-variational inequality model.
Problem
Large sparse LCPs require iterative methods that balance convergence behavior, linear-solve cost, and preservation of sparse, easily solvable coefficient structures.
Method
The method introduces two shift matrices into Bai’s modulus-based splitting, preserving the original LCP coefficient matrix while enabling shifted Jacobi, Gauss-Seidel, SOR, and AOR-type schemes.
Results
Across four tested examples, RSMGS achieves either the best or highly competitive iteration and CPU performance, with residuals of order 10^-6.
Takeaways & Limitations
Admissible shift intervals and grid search provide an effective practical way to select parameter pairs for the tested large-scale sparse LCPs.
Takeaways & Limitations
Fully analytical selection of optimal or nearly optimal shift parameters remains open, and the convergence margin is only sufficient rather than an exact convergence rate.
Abstract
from arXiv · showhide
A relaxed shifted matrix-splitting modulus-based iteration method is proposed for solving large-scale sparse linear complementarity problems. The method extends the classical modulus-based matrix-splitting framework by introducing two shift parameters into the matrix splitting while preserving the original coefficient matrix. Different choices of the splitting lead to shifted Jacobi, Gauss-Seidel, SOR, and AOR-type schemes. Sufficient convergence conditions are established for \(P\)-matrices and \(H_+\)-matrices. For structured sparse matrices, practical AOR-type conditions and explicit admissible intervals for the shift parameters are also derived. These intervals are used together with a grid-search procedure to select efficient parameter pairs. Numerical experiments on four large-scale sparse test problems, including a quasi-variational inequality model, show that the proposed method is competitive with several existing modulus-based and projected methods. A direct comparison with the two-parameter MAOR method further illustrates the effect of the proposed shifted splitting.
1 Introduction
The paper targets large sparse linear complementarity problems, where iterative methods must balance convergence with the cost and sparsity of each linear solve. It introduces a relaxed shifted modulus-based splitting framework that preserves the original problem while tuning the iteration.
- 1 Introduction: Large sparse LCPs arise in optimization, equilibrium, variational inequalities, free-boundary problems, and engineering applications.Discretized models such as American-option pricing can produce large sparse LCPs.
- 1 Introduction: Iterative methods are attractive for large sparse systems because they require less storage and can exploit matrix structure.However, each iteration solves a linear system, so iteration count alone may not reflect total CPU time.
- 1 Introduction: The proposed framework introduces two shift matrices and tunable parameters while leaving the original LCP coefficient matrix unchanged.Shifted splittings are motivated by their use in efficient solvers for other matrix problems.
- 1 Introduction: The shifted method is algebraically different from applying the classical modulus-based method with an AOR splitting.The shifts affect both the linear-system coefficient matrix and the iteration’s linear right-hand-side term.
- 1 Introduction: Convergence results cover P-matrices and H+-matrices, with practical AOR-type conditions and admissible shift intervals for structured sparse matrices.A grid search is used to select efficient parameter pairs, whose sensitivity is examined experimentally.
2 Preliminaries
The preliminaries establish notation for componentwise matrix operations and standard matrix classes, then recall spectral-radius, M-matrix, splitting, and modulus-based fixed-point results used later.
- 2 Preliminaries: The section defines componentwise inequalities, absolute values, Euclidean norms, transposes, inverses, spectral radius, and componentwise minima.These conventions support the later convergence analysis.
- 2 Preliminaries: It introduces comparison matrices, Z-matrices, nonsingular M-matrices, H-matrices, H+-matrices, P-matrices, regular splittings, and H-compatible splittings.H+-matrices additionally require positive diagonal entries, while P-matrices have positive principal minors.
- 2 Preliminaries: The auxiliary lemmas connect spectral-radius bounds with convergence to zero and characterize nonsingular M-matrices through splittings, spectral radius, and positive test vectors.They also provide monotonicity of spectral radius for ordered nonnegative matrices.
- 2 Preliminaries: A modulus-based fixed-point equation is recalled as equivalent to the original LCP under a matrix splitting, positive diagonal matrix, and positive scalar parameter.Both directions of equivalence are stated: an LCP solution yields a fixed-point solution, and conversely.
3 Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method
The method replaces a standard matrix splitting with a shifted splitting whose added terms cancel in the original matrix, while changing the matrices used by the iteration. Relaxation choices produce shifted Jacobi, Gauss-Seidel, SOR, and AOR schemes with sparse implementations and residual-based stopping.
- 3 Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method: The shifted splitting rewrites A = M − N using M + Ω1 − Ω2 and N + Ω1 − Ω2, preserving A while modifying the iteration.The cancellation keeps the original LCP unchanged but changes the matrices used computationally.
- 3 Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method: The relaxed shifted iteration solves a system involving M + Ω1 − Ω2 + γΩ4 and combines the previous iterate, its absolute value, and q.The method starts from Bai’s modulus-based matrix-splitting formulation.
- 3 Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method: The algorithm returns an approximate solution, iteration count, and residual, stopping when the residual falls below ε or reporting nonconvergence after Kmax iterations.The input includes the shifted splitting, auxiliary matrices, γ, an initial vector, tolerance, and iteration limit.
- 3 Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method: The RSMAOR family specializes to RSMJ for (α, β) = (1, 0), RSMGS for (1, 1), and RSMSOR when β = α ≠ 0.These choices instantiate shifted analogues of standard splitting schemes.
4 Convergence Analysis
The proposed shifted modulus-based iteration is analyzed through spectral-radius conditions for P-matrices and H+-matrices, with specialized AOR criteria for structured sparse systems. These results establish convergence to the unique LCP solution under explicit matrix and parameter conditions.
- Special splittings: The AOR framework includes shifted Jacobi, Gauss-Seidel, and SOR schemes through (α, β) = (1, 0), (1, 1), and β = α ≠ 0, respectively.Each special case inherits sufficient convergence conditions by substituting its α and β values into the AOR parameters.
- AOR-type conditions: The AOR-type method converges under s_α,β > ρ(r_α,β|L| + 2|U|), with the condition also ensuring nonsingularity of the shifted system matrix.The proof bounds the iteration matrix using comparison matrices and nonsingular M-matrix properties.
- Structured sparse matrices: For structured sparse matrices satisfying the spectral-scaling property, κ_m = ρ(|L| + |U|) supports explicit AOR convergence conditions when d > κ_m.The property applies to the paper’s four examples, where the relevant block structure preserves the spectral-radius calculation.
- H+-matrix conditions: For H+-matrices, convergence holds if either γΩ4 ≥ D or 0 < γΩ4 < D with ⟨A⟩ + 2γΩ4 − D − |E| a nonsingular M-matrix.The proof uses that every H+-matrix is a P-matrix and bounds the comparison-based iteration matrix.
5 Experimental Analysis
Experiments evaluate RSMGS on four large-scale sparse LCPs using iteration count, CPU time, and residual, with parameter choices guided by admissible intervals and search. Across the tests, RSMGS is efficient and robust, while shifted Gauss-Seidel parameters balance iteration stability and computational cost.
- Selection of Efficient Parameters ϕ1 and ϕ2: RSMGS uses shifted Gauss-Seidel parameters selected from admissible intervals and experimental searches, with Ω1 = ϕ1I and Ω2 = ϕ2L providing a balance between iterations and CPU time.The upper-triangular shift often reduces iterations but incurs much larger CPU time for large m, whereas the diagonal choice is stable but usually slower in iterations.
- Comparison with MAOR: RSMGS differs algebraically from MAOR because ϕ1 and ϕ2 shift the Gauss-Seidel splitting in the coefficient matrix and right-hand-side linear term, while the modulus term remains unchanged.MAOR instead uses AOR parameters that also scale the modulus term and q; the methods coincide only in the unshifted case.
- Results and Discussion: In Example 5.1, RSMGS has the fewest iterations for both µ = 4 and µ = 6, with smaller iteration counts and CPU time than RGTMSOR at the largest sizes.Its CPU time remains competitive across tested sizes, while MB-DSL becomes increasingly expensive as m grows.
- Results and Discussion: For the nonsymmetric Examples 5.2 and 5.3, RSMGS has the lowest or fewer iteration counts and low CPU time, with Example 5.2 residuals remaining of order 10^-6.The same pair (ϕ1, ϕ2) = (−0.75, 1.25) works for both µ values in Example 5.2.
- Results and Discussion: For the quasi-variational inequality in Example 5.4, RSMGS maintains low iterations and consistently small CPU times, outperforming projected methods and avoiding MB-DSL’s large-size CPU growth.This extends the observed effectiveness beyond standard block-tridiagonal problems to an LCP from a continuous optimal-control model.
- Results and Discussion: Across all four examples, RSMGS is best or highly competitive in iteration count and CPU time while maintaining residuals of order 10^-6.Iteration counts remain nearly stable as m increases, supporting its use on the tested large-scale sparse problems.
6 Conclusions and Future Work
The paper proposes RSMGS, which adds two shift matrices without changing the original LCP coefficient matrix, and establishes convergence guidance for large-scale sparse problems. Experiments report efficient and robust performance, while fully analytical parameter selection remains open.
- RSMGS introduces two shift matrices into the splitting without changing the original coefficient matrix, and the resulting Gauss-Seidel-type scheme is used experimentally.The shift parameters are ϕ1 and ϕ2.
- Convergence results cover P-matrices and H+-matrices, with practical AOR-type conditions and admissible shift intervals derived for structured sparse matrices.The selected experimental parameters satisfy the sufficient convergence condition for the tested problems.
- RSMGS is efficient and robust on the tested large-scale sparse problems in iteration count, residual, and CPU time.The sensitivity analysis supports Ω1 = ϕ1I and Ω2 = ϕ2L as preserving sparse Gauss-Seidel structure while balancing convergence speed and computational cost.
- A fully analytical strategy for selecting optimal or nearly optimal shift parameters remains open despite admissible intervals and grid search.Future work also targets implicit, horizontal, and vertical linear complementarity problems.