PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Approximate Selected Inversion Based on Single-Level Incomplete $LDL^T$ Factorization and Spectral Corrections for Large Sparse Systems

Tahamina Akter, Matthias Bollhöfer, Olaf Schenk

arXiv:2609.11363v1math.NAcs.NA

TL;DR

Large sparse applications often need only selected inverse entries rather than a full inverse. The paper combines incomplete-factorization-based selected and approximate inversions, including a mixed SPAI-refined method and optional spectral correction. Its conclusions emphasize matrix-dependent trade-offs among accuracy, sparsity, runtime, and cost.

  • Problem

    Large sparse applications often need only selected entries of the inverse, since explicitly constructing the full inverse destroys sparsity and can be computationally unreasonable.

    Source: §1 · p. 1, §2 · p. 3

  • Method

    The framework builds selected, truncated-Neumann, mixed, and Mix-SPAI inverse approximations on incomplete block LDLT, with optional low-rank correction from dominant residual-inverse-error eigenmodes.

    Source: §1 · p. 2, §2.4 · p. 6

  • Results

    The methods offer matrix-dependent advantages, while spectral correction's effectiveness varies by matrix and must be weighed against eigensolver cost.

    Source: §4 · p. 18

  • Takeaways & Limitations

    The authors conclude that the framework balances accuracy, sparsity, runtime, and computational cost while adapting approximations to matrix numerical behavior.

    Source: §4 · p. 18

    A sufficiently accurate residual eigenpair alone does not guarantee improvement in a target-specific quantity, and indicators of residual-mode alignment warrant further study.

    Source: §3.4 · p. 14, §4.1 · p. 18

Abstract

from arXiv · show

This article introduces four parallel numerical techniques for computing entries of the inverse of large sparse symmetric systems, all grounded in incomplete $LDL^T$ (ILDL) factorizations: (1) the selected inversion method (SelInv), which applies the $LDL^T$ factorization to recover entries of the matrix inverse within the sparsity pattern of the computed factors; (2) an approximate inversion method based on a truncated Neumann series expansion applied to the inverse of the L factor (NInv), providing an alternative at the cost of reduced accuracy; (3) a Mix approximation that merges the best of both SelInv and NInv; and (4) Mix-SPAI, which applies sparse approximate inverse (SPAI) refinement on the output of the Mix method to improve entry-level accuracy. To further improve accuracy while maintaining a stable sparsity pattern, we additionally employ a low-rank correction based on eigenvector updates, providing an alternative to tightening the drop tolerance. We report the performance of the proposed numerical techniques on a comprehensive collection of sparse matrices from scientific and industrial applications.

1 Introduction

Large sparse applications often need only selected entries of an inverse, and approximate values may suffice. This work combines incomplete-factorization-based selected and approximate inversion methods to balance accuracy and computational demands.

1 Introduction

  • Selected inversion targets only needed inverse entries, avoiding construction of the complete inverse for large sparse applications.Applications include sensitivity analysis, electronic-structure calculations, quantum transport, and discretizations of partial differential equations.Source: §1 · p. 1
  • The factorization pattern determines which inverse entries selected inversion computes and stores.The selected index set is induced by the nonzero pattern of L + D + L^T.Source: §1 · pp. 1–2
  • Selected inversion recovers entries within its pattern, whereas approximate inversion can provide information outside it, potentially at an accuracy and memory cost.Source: §1 · p. 2
  • The framework uses incomplete block LDLT for selected inversion, truncated-Neumann approximate inversion, their Mix combination, and optional spectral correction.The four constructions share a block ILDL computational backbone.Source: §1 · pp. 2–3

2 Background and current approaches

This section presents selected and approximate inversion approaches for large sparse systems based on incomplete factorization, with low-rank spectral correction, and defines the quantities used to compare them: diagonal error, factor and inverse fill, and runtime components.

2.1 Selected inversion based on incomplete factorization

  • SelInv recursively computes inverse entries only on the ILDL-induced pattern S; with exact LDL^T it matches A^-1 on S, while incomplete factors yield (LDL^T)^-1 there.The method preserves the incomplete factorization’s sparsity structure rather than constructing the full dense inverse.Source: §2.1 · p. 4

2.2 Approximate inversion using Neumann series

  • NInv approximates L^-1 by truncating and sparsifying its Neumann-series expansion, with inverse tolerance δ controlling the resulting sparsity and fill.Smaller δ retains more entries and produces a denser approximation; looser tolerances give cheaper approximations.Source: §2.2 · pp. 4–5

2.3 Mixed approximate inversion

  • Mix combines NInv’s global sparse approximation with selected inverse values on entries meeting target tolerance ε, balancing their complementary coverage.The approach depends on ILDL drop tolerance τ, NInv tolerance δ, and selection tolerance ε; computing both approximations incurs their combined cost and fill.Source: §2.3 · pp. 5–6

2.4 SPAI Refinement of Approximate Inverses

  • Mix-SPAI starts from a loose-tolerance NInv pattern, overwrites selected entries with SelInv values, then applies parallel, column-wise SPAI refinement without enlarging that pattern.SPAI improves values while keeping the prescribed sparsity pattern fixed.Source: §2.4 · p. 6

2.5 Inversion error and spectral correction

  • A rank-k spectral correction targets dominant modes of the remaining inverse error, removing unresolved modes without increasing sparse ILDL fill.Because the exact inverse is unavailable, the correction uses matrix-free inverse actions with preconditioned Krylov methods; it is useful when dominant error components are captured by few eigenmodes.Source: §2.5 · pp. 7–8

2.6 Measured quantities

  • Approximation quality is assessed using inverse diagonal entries computed in advance by a direct solver, and a correction is retained only if it improves diagonal error.The factored low-rank correction adds O(nk) storage and work for k ≪ n.Source: §2.6 · pp. 8–9
  • The relative diagonal error is measured using an expression that substitutes bdk for bd when the corrected diagonal is accepted.The supplied passage does not include the error expression itself.Source: §2.6 · p. 9
  • The reported sparsity measures are factor fill and inverse fill.Source: §2.6 · p. 9
  • Runtime is split into factorization time, base inverse approximation time, and spectral correction time.Source: §2.6 · p. 9

3 Numerical Experiments

The experiments compare four inverse constructions across sparse test matrices, examining accuracy, fill, runtime, and spectral correction. Results show that the value of spectral correction depends on the matrix and inverse construction, while covariance cases favor Mix-SPAI for diagonal accuracy.

3.1 Experimental and computational setup

  • The experiments use a common block ILDL backbone; SelInv and NInv are parallelized, but the ILDL factorization is sequential and can dominate runtime.Mix uses a cheaper NInv component with δ = 10^-1, while Mix–SPAI applies SPAI refinement on the fixed Mix sparsity pattern.Source: §3.1 · p. 10

3.2 Properties of Test Matrices

  • The test matrices include structural cases that may need spectral correction and strongly diagonally dominant covariance and microbenchmark cases that are often well approximated by the base methods.The microbenchmark matrices are substantially denser than the representative SuiteSparse matrices.Source: §3.2 · p. 10

3.3 Effect of the Drop Tolerance

  • Tightening τ generally improves diagonal accuracy but increases factor fill and runtime; its effect is strong for crankseg_2 and weaker for oilpan and wathen120.All four methods share the same factor fill at a fixed τ, while total runtime also includes inverse construction and eigensolver costs.Source: §3.3 · pp. 10–11

3.4 Performance on Fixed Matrices

  • For pwtk at τ = 10^-5, spectral correction reduces SelInv’s relative diagonal 1-norm error from 6.46×10^-2 to 2.56×10^-2, while Mix accepts no correction.Apache1 also benefits, with the size of the improvement varying by inverse construction.Source: §3.4 · p. 13
  • For oilpan and wathen120, spectral correction yields no accuracy gain; on the dense microbenchmarks, Mix matches SelInv-level accuracy at approximately NInv sparsity.Mix-SPAI has larger errors and extra cost on the microbenchmarks, and no correction is accepted there.Source: §3.4 · p. 14
  • At τ = 10^-5, the fastest approximate construction for crankseg_2 is about 176 times faster than the sparse direct reference, with accuracy–runtime trade-offs across methods.The direct computation also requires repeated triangular solves to recover the complete inverse diagonal.Source: §3.4 · p. 14

3.5 Application to covariance and uncertainty quantification.

  • For uncertainty quantification, selected covariance entries are estimated from the inverse precision matrix, A ≡ Q and A^-1 ≡ Σ; probing is another option for diagonal estimation.Source: §3.5 · pp. 14, 16

3.6 Covariance-type example without deflation

  • Mix-SPAI gives the smallest diagonal error in every displayed covariance case, and no spectral correction is retained in these tests.The accepted errors therefore coincide with the base errors.Source: Figure 11 · p. 17, §3.6 · pp. 17–18

4 Concluding Remarks

The framework balances accuracy, sparsity, runtime, and computational cost through several inverse constructions and optional spectral correction. The authors identify matrix-dependent limits and outline future extensions beyond the single-level block ILDL setting.

4 Concluding Remarks

  • The block ILDL drop tolerance trades inverse accuracy against sparsity, runtime, and computational cost.The numerical experiments identify this tolerance as an important trade-off.Source: §4 · p. 18
  • Spectral correction can improve the approximation, but its effectiveness depends strongly on the matrix and must be weighed against eigensolver cost.The authors retain spectral information only when it yields a measurable improvement.Source: §4 · p. 18
  • The framework combines block ILDL, selected inversion, approximate inverse techniques, and optional spectral correction to balance accuracy, sparsity, runtime, and computational cost.The four inverse constructions are SelInv, NInv, Mixed, and Mix–SPAI; their advantages depend on the matrix and required accuracy.Source: §4 · p. 18

4.1 Future Work

  • The work mainly uses single-level block ILDL; inverse-based multilevel factorizations are proposed as future work to seek a better balance of robustness, fill, and approximation quality.Other proposed directions include target-oriented spectral correction without an exact inverse diagonal, adaptive tolerance and correction-rank selection, and study of Hermitian indefinite systems and residual-mode alignment.Source: §4.1 · p. 18

A Notation

Table 4 collects the paper’s main notation and abbreviations; the listed abbreviations include ILDL, SelInv, NInv, SPAI, PCG, and PRIMME.

A Notation

  • Table 4 is identified as the source for the work’s main notation and abbreviations.The passage lists ILDL, SelInv, NInv, SPAI, PCG, and PRIMME among the abbreviations.Source: A Notation · p. 21, Table 4 · p. 21
  • Table 5 labels the pre-correction and final relative diagonal 1-norm errors as ebase and efinal, respectively.The caption defines Geig as ebase/efinal, kacc as accepted correction rank, and seig as the eigensolver share of total runtime.Source: Table 5 · p. 22
Loading 2609.11363v1…