{"id":"cb74ab86-0631-434a-8114-743227555737","arxiv_id":"2505.20696","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Incomplete Cholesky and its modified variant provide the largest work reduction among black-box preconditioners for CG, but fail on roughly 20% of problems, and AMD matrix ordering substantially outperforms RCM.","lead":"A benchmark of 79 sparse symmetric positive definite systems compares 10 black-box preconditioners in 108 configurations, measuring the floating-point work needed by preconditioned CG. Incomplete Cholesky delivers the largest speedups when it works, but fails on about 20% of matrices, and AMD ordering outperforms the standard RCM ordering.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's 'SPD systems are most likely to benefit from IC' generalizes beyond the filtered test set: all 79 matrices were required to converge with unpreconditioned CG within 10n iterations (Section 5.1), and IC/MIC fail to generate on many large matrices even within that set.","rationale":"The paper is a careful, reproducible benchmark and the authors disclose many limitations: the 10n filter is stated in Section 5.1, the RHS sensitivity is discussed in Section 3.2, and Section 3 explicitly warns that concluding IC/MIC are preferred is premature because generation failures are frequent. Those disclosures are why this is a conditional-accept situation rather than a rejection. The load-bearing issue is external validity: the headline sentence in the abstract removes the qualifiers that the design and the authors' own discussion impose. Every quantitative comparison that supports the headline (Figure 4, Table 7) is defined on the filtered cohort. Since the filter is explicitly based on the behavior of the unpreconditioned solver, it is not a neutral sampling choice; it defines the population of inference. The proposed test directly measures whether the ranking survives on a broader SPD population. A secondary, related source of optimism is that 'best configuration' values in Table 7 are selected in-sample by AUC, so the reported 0.64 is a maximum over configurations rather than an out-of-sample prediction; cross-validated selection in the proposed test would also address this. Neither issue is a correctness flaw in the measurements; both are scope-of-claim problems, which is exactly what a conditional verdict should flag.","tokens_in":34171,"tokens_out":5532,"duration_ms":59371,"concrete_test":"Take all SPD matrices in SuiteSparse with n ≥ 10,000 (or a stratified sample), do not apply the 10n filter, and run the same PCG benchmark with a fixed iteration budget (e.g., max(10n, 100,000) iterations) and the same work metric, counting generation failures as 4× control as Table 7 does. Select the IC and AMG-SA configurations by cross-validation or on a training split, then recompute AUC, ≥2×, ≥4×, and ≥8× on the held-out unfiltered set. If the IC advantage over AMG-SA shrinks below the reported gap (0.64 vs 0.36 AUC) or reverses when generation failures are counted as failures, the abstract must be qualified to the filtered population; if IC still dominates, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central ranking in Table 7 (best IC AUC 0.64 vs AMG-SA AUC 0.36) is computed on a test set defined in Section 5.1 by three filters: n ≥ 10,000, SPD, and unpreconditioned CG convergence within 10n iterations. Footnote 1 states that the remaining SPD matrices are still being studied, an explicit admission that the reported set is a filtered cohort rather than a representative sample of SPD systems. Because the inclusion criterion selects matrices on which plain CG already makes progress, it removes exactly the hard, ill-conditioned systems where a robust preconditioner like AMG should have its best relative showing and where IC is most fragile. Section 3 reports that, even on the filtered set, IC/MIC failed to generate on 12 of the 16 largest matrices and have roughly 15–20% generation-failure rates overall; Table 7's 'Succ.' column is only 84% for the best IC configuration. The abstract's claim is therefore conditional on (i) CG convergence without preconditioning and (ii) successful IC generation, and neither condition appears in the abstract. The claim may be true for the studied cohort, but it is not established for 'symmetric positive definite systems' as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper presents an empirical benchmark of preconditioners for solving large sparse SPD systems with PCG. Using 79 SuiteSparse matrices of dimension at least 10,000, the authors evaluate 10 preconditioner classes in 108 configurations, reporting float-arithmetic work to reduce the relative residual to 1e-10 relative to a Jacobi-scaled unpreconditioned baseline and to an estimated sparse direct solve. The main reported findings are that incomplete Cholesky and modified incomplete Cholesky give the largest work reductions when they can be generated; AMG methods are reliable and occasionally strong; classical SGS/SSOR and SSPAI give little benefit; and including factorization construction costs substantially narrows the advantage over direct methods. The paper also studies the effect of AMD/RCM/natural orderings and of fill-in on incomplete factorizations, and it contains extensive per-matrix convergence plots in an appendix.","tokens_in":34431,"tokens_out":7233,"duration_ms":79700,"significance":"If the headline claims are taken as claims about the studied cohort, the paper is a useful and unusually transparent contribution: it covers a broad set of preconditioner families and configurations, documents the exact work metric, distinguishes single-best from per-matrix tuned choices, separates solve work from construction work, and provides reproducible code and data. The finding that AMD ordering consistently outperforms RCM for incomplete factorizations, contrary to some classical guidance, is interesting and worth reporting. However, the abstract and key findings generalize to 'symmetric positive definite systems' as a whole, while the experimental design explicitly filters to matrices where unpreconditioned CG already converges in at most 10n iterations and where the preconditioners can be generated. The in-sample selection of the 'single-best' configuration also makes the headline numbers optimistic. These issues are fixable with a revision that narrows the claims and adds robustness analysis.","major_comments":[{"comment":"The abstract's headline claim, 'symmetric positive definite systems are mostly likely to benefit from incomplete symmetric factorizations,' is not supported for SPD systems in general. Section 5.1 restricts the test set to matrices for which unpreconditioned CG converges within 10n iterations, and footnote 1 says the remaining SPD matrices are still being studied. Section 3 then explicitly warns that concluding IC/MIC are the preferred preconditioners 'is premature' because they fail to generate on roughly 15–20% of problems and on 12 of the 16 largest matrices; Table 7 shows the best IC configuration has an 84% success rate. The evidence supports a claim about the filtered cohort, not about all SPD systems. The abstract and Section 3 should be reworded to state this conditionality, and the paper should at least discuss how the ranking might change if the excluded hard systems were included.","section":"Abstract and §3"},{"comment":"The 'single-best configuration' is selected and evaluated on the same 79 matrices. Section 2.2 says the single-best configuration is chosen by computing the AUC over all matrices, and Section A.1 defines that AUC over the test set; the same data are then used to report the configuration's parity and 2x/4x/8x rates in Table 7 and Figure 4a. This is in-sample model selection and makes the headline numbers optimistic as estimates of how a fixed configuration would perform on new SPD systems. The authors should use a split or cross-validation for configuration selection, or otherwise quantify the selection bias, before presenting the single-best configuration as a practical recommendation.","section":"§2.2, §A.1, Table 7"},{"comment":"The central ranking of preconditioners rests on the AUC and on the geometric mean, where Table 7 defines failure to generate or converge as 4x control work. No sensitivity analysis is reported for this ad-hoc penalty, and the AUC can be dominated by a few very large speedups, so it is unclear whether the ordering 'IC best, AMG second' is robust. The paper should report additional distributional summaries (e.g., median work reduction, quantiles, and success rates alone) and show how the ranking changes if the 4x penalty is varied or if failed generations are treated as missing rather than as 4x control work.","section":"Table 7 and §2.2"}],"minor_comments":[{"comment":"There are several typos and small wording errors: 'preconditoners' and 'mostly likely' in the abstract, 'availalbe' in Section 3.4, 'matric' in Section 5.3, 'T refethen' in Appendix B headings, and 'MC' instead of 'MIC' in Section 7.1.","section":"Throughout"},{"comment":"The sentence 'The best configurations for each method are summarized in Table 2' should refer to Table 7, since Table 2 lists preconditioner classes rather than configurations.","section":"§2.2"},{"comment":"The caption defines 'Succ.' as the fraction of problems in which the preconditioner was successfully generated, but the geometric-mean definition also treats convergence failure as 4x control work; the caption should clarify whether 'Succ.' includes convergence failures after successful generation or only generation failures.","section":"Table 7 caption"},{"comment":"The paper explicitly limits generation-cost comparisons to methods for which the cost can be estimated, and it correctly notes that AMG construction costs are not included. It would help to add a sentence in Section 3 making clear that the 'including generation cost' conclusions do not apply to AMG or to SSPAI.","section":"§2.3 and §2.6"},{"comment":"The table footnote for the AMG smoothed-aggregation entry states that one iteration of each cycle was best on 2.5% of the test set, but the wording is slightly confusing about whether the percentage refers to being tied for best; consider rewording for clarity.","section":"§7.4"}],"recommendation":"major_revision","confidential_remarks":"The empirical work is careful and the authors are unusually candid about limitations, including the ongoing expansion of the test set and the failure rates of incomplete factorizations. The main issue is that the abstract and discussion overstate the generality of the findings relative to the filtered test set, and the single-best configuration is evaluated in-sample. Both are addressable in revision. The paper is primarily a benchmark contribution rather than a new numerical method; if the journal expects substantial theoretical novelty, the fit should be weighed, but for an empirical study the transparency and reproducibility are strong points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version. This is a useful paper and worth reading, but the abstract overclaims. The study itself is one of the more honest benchmark papers I've seen in this area. The authors run 108 configurations of 10 black-box preconditioners on 79 SPD matrices from SuiteSparse, with a flops-based work metric and performance profiles. The genuinely new bit is the ordering result: for incomplete Cholesky, AMD consistently beats RCM and natural orderings, which goes against the usual guidance (Saad, Duff-Meurant). They back this with a fill-in analysis that holds up. That alone is worth citing.\n\nWhat's soft: the test set in Section 5.1 is filtered to matrices where unpreconditioned CG converges within 10n iterations. That removes exactly the hard, ill-conditioned systems where a robust preconditioner like AMG should look best and where IC is most fragile. Even inside the filtered set, IC/MIC fail to generate on 12 of the 16 largest matrices and about 15-20% of the whole set; Table 7 shows the best IC config succeeds on only 84%. So the abstract's sentence that 'SPD systems are mostly likely to benefit from incomplete symmetric factorizations' is not established for SPD systems generally. It's established for the studied cohort. The paper itself almost says this in Section 3 ('this conclusion is premature'), so the fix is not hard: qualify the abstract and the conclusions to the filtered population.\n\nAlso, the single-best configuration is selected on the same 79 matrices, which is in-sample tuning. They disclose it and separately show tuned-best, but the headline AUCs are still optimistic. RHS sensitivity is acknowledged, and the variance check in Table 4 is thin. The setup-cost comparisons are approximate, and they say so.\n\nNow the credit side: the methodology is transparent, they distinguish single-best from tuned-best, they ship code and data, and they clearly separate generation cost from iteration cost. The limitations section is unusually candid. Prior benchmarks (George et al., Gao et al.) are smaller and narrower, so the field gets real coverage here.\n\nWho should read it: practitioners choosing a preconditioner for a mid-size SPD problem, and anyone writing about ordering strategies. It deserves a serious referee. I'd send it to review with a request to qualify the claims, add the excluded matrices or at least a sensitivity analysis, and consider cross-validating the configuration choice. Not a desk reject.","headline":"A careful, honestly reported benchmark with a genuinely new AMD-over-RCM result, but the abstract's blanket claim about SPD systems outruns the filtered test set.","tokens_in":34976,"tokens_out":2723,"would_cite":true,"duration_ms":28125,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F08","65F10","65F50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This benchmark of 108 preconditioner configurations on 79 symmetric positive definite matrices finds that incomplete Cholesky with AMD ordering yields the most consistent work reductions, with algebraic multigrid reliable but rarely…","keywords":["preconditioned conjugate gradient","incomplete Cholesky","algebraic multigrid","performance profiles","symmetric positive definite systems","matrix ordering","approximate minimum degree","black-box preconditioners"],"falsifier":"Take the SPD matrices of dimension at least 10,000 from the same public sparse-matrix collection the paper used, keep only the ones that fail the $10n$ unpreconditioned-CG filter, and run the same 108 configurations with the same flop-based work metric. If IC/MIC's generation-success rate drops below the roughly 80% seen here, or if smoothed aggregation AMG achieves a higher AUC on that cohort, the paper's broad preference for incomplete Cholesky would not carry over to hard SPD systems.","tokens_in":33924,"feed_emoji":"🧮","tokens_out":8801,"duration_ms":87303,"temperature":0.7,"pith_summary":"This paper asks which black-box preconditioners actually speed up preconditioned conjugate gradient on real symmetric positive definite (SPD) systems, and it answers with a wide benchmark: 79 matrices, 10 preconditioner classes, and 108 configurations measured by floating-point work to reach a relative residual of $10^{-10}$. The central finding is that incomplete symmetric factorizations, especially thresholded incomplete Cholesky (IC) with approximate minimum degree (AMD) ordering, give the most consistent large speedups, while algebraic multigrid is reliable but rarely the fastest. The paper also shows that preconditioner construction cost is a deciding factor: once build effort is counted, the advantage of IC over both plain CG and direct solvers narrows, though tuned IC still wins on most matrices. The practical upshot is that IC should be the default first try for SPD systems where plain CG converges.","feed_headline":"Incomplete Cholesky leads 108-config SPD preconditioner benchmark","feed_subtitle":"On 79 real SPD matrices, tuned incomplete Cholesky cuts solve work at least 2x on 78% of cases.","key_machinery":"The load-bearing measurement is the performance profile: for each preconditioner configuration, the fraction of test matrices where the total work, $\\text{work} = (5n + \\text{nonzeros} + \\text{preconditioner})\\cdot\\text{iterations} + \\text{preconditioner}$, is reduced by at least a factor $\\tau$ relative to the diagonally scaled control, summarized by the area under the curve (AUC) in log2 space. Within that metric, the decisive object is the simplicial incomplete Cholesky factorization, which approximates $A \\approx LL^T$ by keeping only entries above a drop tolerance; its best configuration combines threshold $10^{-8}$ with approximate minimum degree reordering. This object carries the argument because it alone combines large AUC with speedups of 2x or more on most of the test set, and because its generation-failure rate motivates the paper's call for fallback mechanisms.","core_discovery":"The paper's claim is that, over the class of SPD systems it can study, incomplete Cholesky is the most effective preconditioner class even when no per-matrix tuning is allowed. Under a single-best configuration, IC with drop tolerance $10^{-8}$ and AMD ordering achieves an AUC of 0.64, cuts total work by at least a factor of 2 on 78% of the 79 matrices, and reaches at least 8x on 62%; modified IC is close behind with AUC 0.61. Smoothed aggregation AMG, the best multigrid option, has AUC 0.36 and reaches 2x on only 38% of matrices, though it generates successfully on essentially all problems while IC and MIC fail to factor about 16-19% of the time. Classical SGS and SSOR preconditioners do not pay off, and unpreconditioned CG already beats an estimated direct solve by 2x on roughly 47% of matrices. The authors further claim that including construction cost shrinks but does not eliminate IC's edge, and that AMD ordering outperforms both RCM and natural orderings for incomplete factorizations, contradicting the usual preference for RCM.","pith_inferences":["Editorial inference: the $10n$ convergence filter likely biases the test set toward matrices where IC works, so the paper's headline claim should be read as 'IC is best among SPD systems that are already tractable for CG,' not as a universal SPD statement.","Editorial inference: the work metric counts floating-point operations but not memory traffic or parallelism; a wall-clock study on multicore machines could narrow or reverse IC's margin over direct solvers, since sparse factorization is more parallelizable than the serial PCG recurrence.","Editorial inference: the AMD-over-RCM result suggests a testable extension: compare IC with nested-dissection orderings at larger scales, where the authors' own data shows IC generation failing on 12 of the 16 largest matrices.","Editorial inference: the success-parity numbers imply a natural hybrid strategy\\u2014start with IC/AMD, fall back to AMG when generation or convergence fails\\u2014that would likely combine IC's speed with AMG's near-universal reliability on this test set."],"forward_implications":["A user facing an SPD system where plain CG converges should try thresholded incomplete Cholesky with AMD ordering before anything else: the single-best IC configuration, drop tolerance $10^{-8}$ with AMD, gives at least a 2x work reduction on 78% of the benchmark matrices.","Symmetric Gauss-Seidel and SSOR are a poor investment as black-box preconditioners; even their tuned variants produce large speedups on under 10% of problems.","Algebraic multigrid is the most dependable fallback because it generates on 100% of test matrices and reaches parity with the baseline on 89-96%, even though its top speedups are smaller than IC's.","Including preconditioner construction cost changes the practical message: with a single fixed configuration, only about 28% of problems retain a 4x total-work improvement, so per-matrix tuning or a build-cost-aware choice matters.","Even the unpreconditioned baseline is competitive with direct solves on a large share of the test set, so direct solvers should not be assumed superior without measurement."],"supporting_citations":[{"why":"supplies the public sparse-matrix collection from which the 79 test matrices are drawn.","marker":"Davis and Hu, 2011"},{"why":"introduces incomplete Cholesky, the preconditioner class the paper finds most effective.","marker":"Meijerink and van der Vorst, 1977"},{"why":"is the survey that frames the field and the prior guidance on ordering that the AMD result challenges.","marker":"Benzi, 2002"},{"why":"provides the standard text on preconditioned Krylov methods, including the classical preference for RCM ordering.","marker":"Saad, 2003"},{"why":"is the closest prior SPD preconditioner benchmark whose 30-matrix, low-iteration design this study extends.","marker":"George, Gupta, and Sarin, 2012"},{"why":"defines the Ruge-Stüben algebraic multigrid method evaluated here.","marker":"Ruge and Stüben, 1987"},{"why":"defines smoothed aggregation algebraic multigrid, the strongest multigrid baseline in the comparison.","marker":"Vaněk, Brezina, and Mandel, 2001"},{"why":"is the classical empirical study that favored RCM ordering and that the paper's AMD result calls into question.","marker":"Duff and Meurant, 1989"}],"fun_headline_variants":["Incomplete Cholesky wins SPD preconditioner benchmark across 79 matrices","AMD ordering makes incomplete Cholesky outperform RCM in SPD test","Incomplete Cholesky beats multigrid and classical in SPD benchmark","IC preconditioner cuts SPD solve work 2x on 78% of 79 matrices","Tuned incomplete Cholesky beats direct solves despite build costs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole comparison is run on a filtered set of SPD matrices where plain conjugate gradient converges within $10n$ iterations, so the conclusions about 'SPD systems' depend on that slice being representative; if the harder excluded matrices were added, incomplete factorizations would likely fail more often and the ranking could shift.","fun_headline_variants_meta":{"raw":{"variants":["Incomplete Cholesky wins SPD preconditioner benchmark across 79 matrices","AMD ordering makes incomplete Cholesky outperform RCM in SPD test","Incomplete Cholesky beats multigrid and classical in SPD benchmark","IC preconditioner cuts SPD solve work 2x on 78% of 79 matrices","Tuned incomplete Cholesky beats direct solves despite build costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000683,"raw_usage":{"total_tokens":3153,"prompt_tokens":1049,"completion_tokens":2104,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":665,"completion_tokens_details":{"reasoning_tokens":2007}},"tokens_in":665,"tokens_out":2104,"duration_ms":13525,"temperature":1.0,"reasoning_tokens":2007,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:48:53.314028+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the SPD matrices of dimension at least 10,000 from the same public sparse-matrix collection the paper used, keep only the ones that fail the $10n$ unpreconditioned-CG filter, and run the same 108 configurations with the same flop-based work metric. If IC/MIC's generation-success rate drops below the roughly 80% seen here, or if smoothed aggregation AMG achieves a higher AUC on that cohort, the paper's broad preference for incomplete Cholesky would not carry over to hard SPD systems.","supporting_citations":[],"review_version":1}