Pith. sign in

REVIEW 2 major objections 1 minor 1 cited by

An algebraic multiscale preconditioner for large sparse SPD matrices

T0 review · 2 major / 1 minor · reviewed 2026-06-28 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A two-grid algebraic multiscale preconditioner builds its coarse space directly from the matrix via graph partitioning and local eigenvalue solves to handle high-contrast elliptic problems without geometry.

desk verdict This algebraic two-grid preconditioner builds a coarse space from matrix-graph partitioning plus local generalized eigenproblems, but the robustness claim for high-contrast elliptic problems looks vulnerable when channels cross partitions. read the letter →

arxiv 2606.04864 v1 pith:DC5422KV submitted 2026-06-03 math.NA cs.NA

Yingjie Zhou , Shubin Fu , Eric Tsz Shun Chung This is my paper · ORCID
classification math.NAcs.NA
keywords algebraicmultiscalepreconditionersymmetricpositivedefinitematricesheterogeneouscoefficientsgraphpartitioninggeneralizedeigenvalueproblemsDarcyflowparallelscalabilitymultigridmethods
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces a two-grid algebraic multiscale preconditioner designed for large sparse symmetric positive definite matrices that arise from elliptic partial differential equations with highly heterogeneous coefficients. It constructs the necessary coarse space directly from the matrix entries using graph partitioning to divide the problem and local generalized eigenvalue problems to identify important modes. This construction avoids any need for underlying geometric information, which makes the method applicable to unstructured grids or situations where only the matrix is available. The authors demonstrate through numerical experiments on heterogeneous Darcy flow that the resulting preconditioner maintains robustness across varying coefficient contrasts and problem sizes while showing better performance than standard algebraic multigrid approaches on difficult large-scale problems and exhibiting good parallel scalability.

What carries the argument

Graph partitioning of the matrix followed by local generalized eigenvalue solves to generate coarse basis functions that capture low-energy modes.

What would settle it

A Darcy flow test with extreme coefficient contrast where the number of preconditioned Krylov iterations fails to decrease or grows as the contrast ratio increases.

Watch

Extended reading notes

Core claim

The central discovery is a two-grid algebraic multiscale preconditioner whose coarse space is obtained by graph partitioning the system matrix and solving local generalized eigenvalue problems on the resulting subdomains. This produces basis functions that capture the low-energy modes responsible for slow convergence in highly heterogeneous elliptic problems. The method operates without geometric information and is naturally parallelizable in its construction.

Load-bearing premise

The coarse space from graph partitioning and local generalized eigenvalue solves will reliably capture the global low-energy modes responsible for slow convergence in highly heterogeneous elliptic problems.

Editorial extensions

If this is right

  • The preconditioner remains robust with respect to coefficient contrast and problem size for heterogeneous Darcy flow problems.
  • It outperforms standard algebraic multigrid on challenging large-scale cases.
  • Construction and application exhibit good parallel scalability.
  • The method applies directly to unstructured meshes and matrix-only inputs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same partitioning-plus-local-eigenvalue construction could be tested on other elliptic operators such as linear elasticity or anisotropic diffusion.
  • Replacing the two-grid structure with a recursive multilevel version might further improve scalability for problems exceeding current test sizes.
  • The approach may combine with existing sparse-direct or iterative solvers in standard libraries to reduce overall setup time.
  • Varying the number of eigenvectors retained per subdomain offers a tunable parameter for trading setup cost against iteration count.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a two-grid algebraic multiscale preconditioner for large sparse SPD matrices from elliptic problems with highly heterogeneous coefficients. The coarse space is constructed directly from the system matrix via graph partitioning followed by local generalized eigenvalue solves on the subdomains, producing basis functions that capture low-energy modes. The approach requires no geometric information, is naturally parallelizable, and is tested on heterogeneous Darcy flow problems, where it is reported to be robust to coefficient contrast and problem size, to outperform standard algebraic multigrid on large-scale cases, and to exhibit good parallel scalability.

Significance. If the central construction reliably extracts the slow modes and the reported numerical behavior generalizes, the method would supply a purely algebraic two-grid preconditioner usable in matrix-only and unstructured settings where geometric multiscale techniques are unavailable. The emphasis on parallel construction and the direct comparison to AMG on challenging heterogeneous cases are concrete strengths that could influence preconditioner design for large-scale elliptic problems.

major comments (2)
  1. [Abstract and method description] Abstract and method description: the claim that local generalized eigenvalue problems on graph-partitioned subdomains capture the global low-energy modes responsible for slow convergence is load-bearing for the robustness statement. Because the partitioning uses the unweighted matrix graph, a high-conductivity channel that crosses subdomain boundaries is split; each local eigenproblem then sees only a truncated segment and cannot produce the corresponding global mode. This directly affects whether the reported robustness to arbitrary coefficient contrast holds.
  2. [Numerical results section] Numerical results section: the superiority to standard AMG and the robustness claims are supported only by the presented Darcy-flow experiments. Without additional tests that deliberately place high-contrast channels across partition boundaries (or an a-priori argument that the local eigenproblems still recover the necessary modes), the generalization from the reported cases to the full class of heterogeneous coefficients remains unverified.
minor comments (1)
  1. [Abstract] The abstract states that the construction is 'naturally parallelizable' but does not quantify the communication pattern or the scaling of the local eigen-solves with subdomain size; a brief remark on this point would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The two major comments identify a substantive issue with the justification of the method's robustness. We respond point by point below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract and method description] Abstract and method description: the claim that local generalized eigenvalue problems on graph-partitioned subdomains capture the global low-energy modes responsible for slow convergence is load-bearing for the robustness statement. Because the partitioning uses the unweighted matrix graph, a high-conductivity channel that crosses subdomain boundaries is split; each local eigenproblem then sees only a truncated segment and cannot produce the corresponding global mode. This directly affects whether the reported robustness to arbitrary coefficient contrast holds.

    Authors: We agree that the unweighted graph partitioning can split high-conductivity channels and that each local eigenproblem therefore sees only a truncated segment. The manuscript's claim that the local solves capture the global low-energy modes is therefore not accompanied by a rigorous argument that the assembled coarse space recovers the necessary global modes when such splitting occurs. We will revise the method-description section to remove the unqualified statement that the basis functions capture the global low-energy modes and instead describe precisely what the local eigenproblems compute. We will also add a short discussion of the limitation introduced by unweighted partitioning. revision: yes

  2. Referee: [Numerical results section] Numerical results section: the superiority to standard AMG and the robustness claims are supported only by the presented Darcy-flow experiments. Without additional tests that deliberately place high-contrast channels across partition boundaries (or an a-priori argument that the local eigenproblems still recover the necessary modes), the generalization from the reported cases to the full class of heterogeneous coefficients remains unverified.

    Authors: The existing numerical section contains only the Darcy-flow suite; no experiments deliberately place high-contrast channels across the partition boundaries produced by the unweighted graph partitioner. We will add a new subsection with two such test cases (one 2-D and one 3-D) in which a high-conductivity channel is forced to cross multiple subdomain interfaces. The revised manuscript will report iteration counts and timings for these cases alongside the original suite, allowing the reader to assess whether the observed robustness persists under the splitting scenario identified by the referee. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: construction is explicit and results are empirical

full rationale

The paper defines its preconditioner directly via graph partitioning of the input matrix followed by local generalized eigenproblems on the resulting subdomains. This is a constructive algorithm, not a derivation that reduces to its own outputs. Numerical experiments on Darcy problems are presented as validation of the resulting method's performance, with no fitted parameters renamed as predictions, no self-citation load-bearing the central claim, and no uniqueness theorems invoked. The derivation chain is self-contained as a matrix-only algebraic procedure whose correctness is assessed externally by the reported timings and iteration counts.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

Based solely on the abstract; no free parameters or invented entities are mentioned. The approach relies on standard domain assumptions about SPD matrices and elliptic problems.

assumptions (2)
  • domain assumption The linear systems are symmetric positive definite and arise from elliptic problems with highly heterogeneous coefficients.
    Stated as the problem class for which the preconditioner is designed.
  • domain assumption Low-energy modes captured by local eigenproblems are responsible for slow convergence of iterative solvers.
    Underlies the rationale for the coarse space construction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An algebraic multiscale preconditioner for large sparse SPD matrices." pith.science (2026). https://pith.science/paper/DC5422KV

@misc{pith2026260604864,
  author       = {Pith},
  title        = {Pith review of: An algebraic multiscale preconditioner for large sparse SPD matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DC5422KV}},
  note         = {Machine review of arXiv:2606.04864}
}
read the original abstract

We present a two-grid algebraic multiscale preconditioner for large sparse symmetric positive definite systems arising from elliptic problems with highly heterogeneous coefficients. The coarse space is constructed directly from the system matrix by graph partitioning and local generalized eigenvalue solvers, yielding basis functions that capture the low-energy modes responsible for slow convergence. The method requires no geometric information, making it suitable for unstructured and matrix-only settings, and its construction is naturally parallelizable. Numerical results for heterogeneous Darcy flow problems show robustness with respect to coefficient contrast and problem size, better performance than standard algebraic multigrid on challenging large-scale cases, and good parallel scalability.

Figures

Figures reproduced from arXiv: 2606.04864 by the authors.

Figure 1
Figure 1. Graph partition examples using METIS to get 64 subdomains of the grid. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 3
Figure 3. We conduct both strong and weak scalability tests, and the results [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 2
Figure 2. First kind of permeability field with long channels. [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figures from the paper (3 more)
Figure 3
Figure 3. Figure 3: Second kind of permeability field with fractures. [PITH_FULL_IMAGE:figures/full_fig_p015_3.png]
Figure 4
Figure 4. Figure 4: Strong and weak scalability results for the proposed preconditioner. The problem [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Strong and weak scalability results for the proposed preconditioner. The problem [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. AlgMortar: a fully algebraic multiscale mortar preconditioner

    math.NA 2026-07 conditional novelty 6.0 of 10

    AlgMortar constructs a fully algebraic, provably well-posed multiscale mortar preconditioner from the SPD matrix alone, and on high-contrast Darcy-flow and SPE11 corner-point systems it is competitive with BoomerAMG.

Reference graph

Works this paper leans on

18 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    T. Y. Hou, X.-H. Wu, A multiscale finite element method for elliptic problems in composite materials and porous media, Journal of compu- tational physics 134 (1) (1997) 169–189. 20

    1997

  2. [2]

    Chung, Y

    E. Chung, Y. Efendiev, T. Y. Hou, Multiscale Model Reduction, Springer, 2023

    2023

  3. [3]

    Efendiev, J

    Y. Efendiev, J. Galvis, T. Y. Hou, Generalized multiscale finite element methods (gmsfem), Journal of computational physics 251 (2013) 116– 135

    2013

  4. [4]

    Jenny, S

    P. Jenny, S. Lee, H. A. Tchelepi, Multi-scale finite-volume method for elliptic problems in subsurface flow simulation, Journal of computational physics 187 (1) (2003) 47–67

    2003

  5. [5]

    Hajibeygi, P

    H. Hajibeygi, P. Jenny, Multiscale finite-volume method for parabolic problems arising from compressible multiphase flow in porous media, Journal of Computational Physics 228 (14) (2009) 5129–5147

    2009

  6. [6]

    S. Fu, E. Chung, L. Zhao, An adaptive preconditioner for three- dimensional single-phase compressible flow in highly heterogeneous porous media, Multiscale Modeling & Simulation 22 (1) (2024) 155–177

    2024

  7. [7]

    C. Ye, S. Fu, E. T. Chung, J. Huang, A robust two-level overlapping preconditioner for darcy flow in high-contrast media, SIAM Journal on Scientific Computing 46 (5) (2024) A3151–A3176

    2024

  8. [8]

    C. Ye, S. Fu, E. T. Chung, J. Huang, A highly parallelized multiscale preconditioner for darcy flow in high-contrast media, Journal of Com- putational Physics 522 (2025) 113603

    2025

Show all 18 references
  1. [9]

    Y. Zhou, C. Ye, Y. Liu, S. Fu, E. T. Chung, A robust solver for large-scale heat transfer topology optimization, arXiv preprint arXiv:2410.06850 (2024)

    2024

  2. [10]

    Heinlein, K

    A. Heinlein, K. Smetana, Algebraic construction of adaptive coarse spaces for two-level schwarz preconditioners, SIAM Journal on Scien- tific Computing 47 (2) (2025) A1170–A1197

    2025

  3. [11]

    Y. Wang, H. Hajibeygi, H. A. Tchelepi, Algebraic multiscale solver for flow in heterogeneous porous media, Journal of Computational Physics 259 (2014) 284–303

    2014

  4. [12]

    J. Xu, L. Zikatanov, Algebraic multigrid methods, Acta Numerica 26 (2017) 591–721. 21

    2017

  5. [13]

    Boffi, F

    D. Boffi, F. Brezzi, M. Fortin, et al., Mixed finite element methods and applications, Vol. 44, Springer, 2013

    2013

  6. [14]

    Arbogast, M

    T. Arbogast, M. F. Wheeler, I. Yotov, Mixed finite elements for elliptic problems with tensor coefficients as cell-centered finite differences, SIAM Journal on Numerical Analysis 34 (2) (1997) 828–852

    1997

  7. [15]

    Anderson, J

    R. Anderson, J. Andrej, A. Barker, J. Bramwell, J.-S. Camier, J. Cer- veny, V. Dobrev, Y. Dudouit, A. Fisher, T. Kolev, et al., Mfem: A modular finite element methods library, Computers & Mathematics with Applications 81 (2021) 42–74

    2021

  8. [16]

    Karypis, V

    G. Karypis, V. Kumar, Metis: A software package for partitioning un- structured graphs, partitioning meshes, and computing fill-reducing or- derings of sparse matrices (1997)

    1997

  9. [17]

    Hernandez, J

    V. Hernandez, J. E. Roman, V. Vidal, Slepc: A scalable and flexible toolkit for the solution of eigenvalue problems, ACM Transactions on Mathematical Software (TOMS) 31 (3) (2005) 351–362

    2005

  10. [18]

    X. S. Li, J. W. Demmel, Superlu_dist: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS) 29 (2) (2003) 110–140. 22

    2003

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.