{"id":"5fc3532e-0269-4334-a34d-c0a14b49a359","arxiv_id":"1908.04081","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors present an adaptive s-step CG variant that uses incremental Ritz value estimates to dynamically update basis parameters and set a formerly heuristic constant, improving reliability and reducing synchronization counts in experiments.","lead":"This paper improves a synchronization-reducing variant of the conjugate gradient method for solving symmetric positive definite linear systems. By continuously estimating extreme eigenvalues during the iterations, it builds better polynomial bases and automatically tunes a key parameter, leading to fewer communication points in many test cases.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4.6 uses the smallest Ritz value, an upper bound on λ_min, as a lower bound μ≤λ_min, so ~ξ can underestimate the true error/residual ratio and undercut the accuracy safeguard.","rationale":"The reader identified the finite-precision reliability of the Ritz estimates as the weak assumption, specifically noting that ~λ_min must not overestimate λ_min. My review confirms and sharpens this: the paper's own derivation requires μ≤λ_min, but the Ritz value it uses is an upper bound, so the inequality in (4.6) is backwards. This is a load-bearing concern because the central reliability claim (attaining a user-specified accuracy) is justified only through the break criterion (4.7), and a too-small c can allow excessive s_k and loss of attainable accuracy. The concern does not refute the empirical improvement results, which are clearly valuable, but it does mean the analysis does not support the claimed guarantee. Since the reader already placed the verdict at CONDITIONAL and this concern is addressable by a concrete numerical check, I do not move the verdict.","tokens_in":20248,"tokens_out":4962,"duration_ms":53578,"concrete_test":"Rerun the nos1 experiment of Section 5.1 in high precision (or with exact arithmetic on a diagonal SPD matrix with known eigenvalues logarithmically spaced from 1e-6 to 1) with Algorithm 5 instrumented to report, at every inner iteration before convergence, both ~ξ computed from (4.6) and the true ξ=||A|| ||x_i−x||/||r_i|| using the known exact solution. Check whether ~ξ<ξ occurs in any iteration; if it does, then c_{m+j+1} is not a valid upper bound, and check whether the full algorithm still reaches ε* in that case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The improved algorithm's reliability rests on the break criterion (4.7), where c_{m+j+1}=max{1, ~λmax (ψ/~λmin)^{1/2}} is meant to bound ξ=||A|| ||x−x̂||/||r̂|| from above. The derivation in Section 4 invokes a bound ||x−x̂|| ≤ ||r̂||/(μ^{1/2} ψ^{1/2}) requiring 0<μ≤λ_min, and then takes μ=~λ_min from (4.2). But ~λ_min=λ_min(T_i), the smallest Ritz value, satisfies λ_min(T_i) ≥ λ_min(A) in exact arithmetic by the Rayleigh–Ritz (interlacing) property. Hence ~λ_min is an upper bound on λ_min, not a lower bound. Substituting it into the denominator of (4.6) makes ~ξ an underestimate of ξ. The condition (4.7) is therefore less conservative than intended: with c too small, the algorithm may keep a larger s_k than (3.1) permits, so the claimed guarantee of attaining the user-specified accuracy is not substantiated. The numerical experiments may not reveal this because the Ritz estimates happen to be sufficiently accurate on those test matrices, or because the adaptive mechanism compensates, but the internal inconsistency is present already in exact arithmetic; finite‐precision s‐step CG can only make the estimates less predictable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an improved adaptive s-step conjugate gradient algorithm for SPD linear systems. It uses incremental estimates of the largest and smallest Ritz values, following Meurant and Tichý, to dynamically update Newton or Chebyshev basis parameters and to replace the previously user-supplied constant c_k by an automatically updated quantity c_{m+j+1} based on Eq. (4.6). The authors present numerical experiments on several small SuiteSparse matrices showing that the improved algorithm often converges to the requested accuracy with fewer outer iterations (global synchronizations) than fixed s-step CG and the previous adaptive s-step CG, while also honestly reporting a difficult case (nos1).","tokens_in":20552,"tokens_out":7075,"duration_ms":76919,"significance":"If the claims hold, the contribution is practically relevant: it removes one heuristic parameter from adaptive s-step CG and improves basis conditioning without user-supplied spectral information. The paper's strengths include a clear experimental setup, comparison against both classical HSCG and the prior adaptive algorithm, a range of tolerances and matrix sizes, and an honest discussion of cases where the improved method is not beneficial. The main weakness is that the derivation of the safeguard c_{m+j+1} in Section 4 contains a bound-direction error, so the central reliability claim is not theoretically substantiated; the experiments are encouraging but cannot by themselves close this gap.","major_comments":[{"comment":"The substitution mu = tilde_lambda_min is invalid for the stated purpose. The bound quoted from [33] requires 0 < mu <= lambda_min(A), but in exact arithmetic the smallest Ritz value lambda_min(T_i) of the Lanczos tridiagonal matrix satisfies lambda_min(T_i) >= lambda_min(A) by the Rayleigh–Ritz (interlacing) property. Hence tilde_lambda_min in (4.2) is an upper bound, not a lower bound, for lambda_min(A). Consequently the quantity tilde_xi in (4.6) can be smaller than the true ratio xi in (4.4), and the break test (4.7) can allow an s_k that violates the sufficient condition (3.1). The claim that the improved algorithm attains the user-specified accuracy is therefore not substantiated. The experiments do not test this safeguard directly, because Figure 2 plots tilde_xi against the global bounds 1 and kappa(A), not against the true xi.","section":"Section 4, Eq. (4.6) and Algorithm 5, lines 20–25"},{"comment":"The incremental Ritz estimates are computed from the alpha and beta coefficients generated inside the finite-precision s-step inner loop (Algorithm 5, lines 13–17). No finite-precision analysis is provided for these estimates in the s-step setting, where the computed coefficients and coordinate recurrences can be amplified by kappa(Y_hat_{k,s}). Since both the basis parameter update (line 29) and the safeguard c_{m+j+1} (line 23) depend on these estimates, the paper does not establish that the dynamic bases are better conditioned than monomial bases in finite precision, nor that (4.7) enforces (3.1). I would ask for an explicit perturbation analysis, even a preliminary one, or for a clear statement that the dynamic basis update is heuristic and outside the scope of the theoretical guarantee.","section":"Section 4 (Algorithms 3–4) and Section 5"}],"minor_comments":[{"comment":"The value of c_k used for the old adaptive s-step CG baseline is not stated; since this heuristic strongly affects the number of inner iterations, please specify it for reproducibility.","section":"Section 5, Tables 2–7"},{"comment":"The initial value c_1 = epsilon^{-1/2} is not derived or explained; please justify this choice or label it as a default heuristic.","section":"Algorithm 5, line 1"},{"comment":"The phrase 'approximately bound' is ambiguous: a bound is either valid or not. Given the issue raised above, please rephrase this to say explicitly that the quantity is heuristic, or provide a certified upper bound.","section":"Section 4, before Eq. (4.6)"},{"comment":"The statement that the total number of iterations is 'independent of sigma' is not strictly true for all reported cases; for example, in Table 7 (nos1, epsilon* = 1e-6, Newton basis) the totals are 1217, 1290, and 1086 for sigma = 5, 10, 15. Please qualify this claim.","section":"Section 5.3"}],"recommendation":"major_revision","confidential_remarks":"This is a credible algorithmic paper, but the inequality-direction error in Section 4 is load-bearing because the paper's reliability argument depends on (4.7) implementing (3.1). I recommend major revision. If the authors can replace the Ritz-based mu with a certified lower bound on lambda_min, or explicitly reframe the safeguard as heuristic and temper the accuracy guarantee accordingly, I would be willing to reconsider."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper is worth reading: it gives a concrete, sensible improvement to adaptive s-step CG by feeding incremental Ritz estimates into the basis construction and using them to set the safety parameter c that was previously heuristic. The experiments are honest and well-chosen; the author includes a case (nos1) where the improved method is not clearly better and explicitly says the experiments are only on small matrices. The core numerical story, that dynamically updated Newton/Chebyshev bases reduce the number of outer-loop synchronizations relative to fixed s-step and the older adaptive scheme, is supported by the data.\n\nThe soft spot is in the theory behind the new automatic setting of c. The bound from Meurant–Tichy requires a lower bound μ ≤ λ_min, but (4.6) substitutes ~λ_min, the smallest Ritz value, which by interlacing is an upper bound on λ_min. So ~ξ is an underestimate of the intended upper bound on ξ, and the break criterion (4.7) is less conservative than the text implies. The claimed guarantee that the user-specified accuracy will be attained is not substantiated. This is a real gap, not a cosmetic one, because that c is the mechanism that controls the inner-loop break. The experiments may be unaffected because the Ritz estimates happen to be accurate on these test matrices, but the derivation should be fixed or the claim explicitly downgraded to a heuristic.\n\nMinor issues: no finite-precision analysis of the Ritz estimates inside the s-step inner loop; the initial c_1 is a heuristic; no code or parallel results. These are addressable.\n\nWho this is for: anyone working on communication-avoiding Krylov methods, particularly s-step CG. The algorithmic idea and the experimental setup are valuable even with the theoretical caveat. It deserves a serious referee; I would send it to review with a request to fix the bound direction and soften the guarantee claims.","headline":"A genuinely useful algorithmic improvement with an honest experimental section, but the new automatic safety parameter rests on a bound that goes in the wrong direction.","tokens_in":21062,"tokens_out":4187,"would_cite":true,"duration_ms":39511,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","65F50","65Y05","65Y20"],"pacs":[],"model":"deepseek-v4-flash","headline":"An adaptive s-step conjugate gradient algorithm that rebuilds its Newton or Chebyshev bases from incremental Ritz-value estimates meets user-specified accuracy with fewer global synchronizations than the previous adaptive s-step method.","keywords":["conjugate gradient","s-step methods","Krylov subspace methods","communication-avoiding algorithms","Ritz value estimation","Newton basis","Chebyshev basis","finite precision accuracy"],"falsifier":"On a small symmetric positive definite matrix with an isolated smallest eigenvalue, record $\\widetilde{\\lambda}_{\\min}$ from Algorithm 4 at every inner iteration before convergence and compare it with the true $\\lambda_{\\min}(A)$ from a high-precision eigensolver. If $\\widetilde{\\lambda}_{\\min} > \\lambda_{\\min}(A)$ at any such iteration, the premise behind the bound (4.6) is violated; one can then check whether the residual gap exceeds the bound (2.10) or the algorithm fails to reach the requested tolerance while standard CG succeeds.","tokens_in":20049,"feed_emoji":"⚡","tokens_out":10209,"duration_ms":88818,"temperature":0.7,"pith_summary":"Communication overloads parallel conjugate gradient iterations, and s-step variants cut synchronization points at the cost of worse finite-precision behavior because the Krylov bases they build can become ill-conditioned. This paper claims that the previous adaptive s-step CG algorithm can be improved by computing cheap incremental estimates of the largest and smallest Ritz values during the iteration and using them to refresh the Newton or Chebyshev polynomial basis parameters after each outer loop. The same estimates replace a previously heuristic constant that controls when the inner loop must stop, turning a user-supplied parameter into a computable quantity. In experiments on small symmetric positive definite test problems, the improved algorithm reached the requested accuracy in every configuration tested, while fixed s-step CG and the old adaptive version often stagnated or diverged for larger step sizes, and it did so with fewer outer-loop synchronization points in many cases.","feed_headline":"Ritz-value tracking keeps s-step CG accurate with fewer syncs","feed_subtitle":"A new adaptive variant rebuilds Newton or Chebyshev bases mid-run and hits user accuracy in tests.","key_machinery":"The object that carries the argument is the s-step Krylov basis matrix $\\widehat{Y}_{k,s}$ and its Gram matrix $G_{k,s}=\\widehat{Y}_{k,s}^T\\widehat{Y}_{k,s}$, whose condition number governs the finite-precision residual gap through the bound (2.10). The mechanism that keeps that condition number under control is the incremental estimation of the extreme Ritz values from the bidiagonal factor $L_i$ of the Lanczos matrix, combined with the scalar recurrence for $\\psi_{m+j+1}$ that produces the adaptive constant $c_{m+j+1}$ from (4.6). These ingredients set the recurrence coefficients $\\theta$, $\\gamma$, $\\mu$ for the Newton or Chebyshev bases and determine when the inner loop should stop, using the largest residual norm seen so far in the current outer loop.","core_discovery":"The paper's central claim is that incremental estimates $\\widetilde{\\lambda}_{\\min}$ and $\\widetilde{\\lambda}_{\\max}$, obtained from the bidiagonal Cholesky factor of the Lanczos tridiagonal matrix as the CG recurrences run, are sufficient to keep the s-step bases well conditioned and to set the inner-loop stopping rule automatically. Concretely, the algorithm builds Newton parameters by (2.7) or simplified Chebyshev parameters by (2.8), and sets $c_{m+j+1}=\\max\\{1, \\widetilde{\\lambda}_{\\max}(\\psi_{m+j+1}/\\widetilde{\\lambda}_{\\min})^{1/2}\\}$ with $\\psi_{m+j+1}=\\psi_{m+j}/(\\psi_{m+j}+\\beta_{m+j})$, which approximates the exact ratio $\\xi_{m+j+1}=\\|A\\|\\,\\|x-\\widehat{x}_{m+j+1}\\|/\\|\\widehat{r}_{m+j+1}\\|$. With this choice the paper argues that the basis condition-number bound can be enforced without user-supplied spectral information or a heuristic constant, and the numerical experiments support the claim that the resulting algorithm attains the prescribed accuracy with fewer global synchronizations than the earlier approach.","pith_inferences":["If the finite-precision reliability of the incremental Ritz estimates were proven inside the s-step inner loop, the same dynamic basis restart idea could be transferred to s-step GMRES, s-step BiCGSTAB, or s-step Lanczos eigensolvers, where basis conditioning plays the same role.","The adaptive formula for $c_{m+j+1}$ is essentially an estimate of the error-to-residual ratio; a direct test of its robustness would compare $\\widetilde{\\lambda}_{\\min}$ from Algorithm 4 against the true smallest eigenvalue early in the iteration, because an overestimate would weaken the bound (4.6).","The observed near-independence of total iterations from $\\sigma$ suggests that an autotuner could safely choose a large maximum step size and let the adaptive loop trim $s$, simplifying parameter selection.","A high-performance parallel implementation on a realistic machine is the natural next test: the paper's experiments are small and report synchronization counts as a proxy rather than wall-clock time."],"forward_implications":["For the tested matrices, the improved algorithm converged to the prescribed accuracy in every case, while fixed s-step CG and the old adaptive algorithm frequently stagnated or diverged at $\\sigma=10$ or $\\sigma=15$.","The number of outer-loop iterations, a proxy for global synchronizations, decreased as the maximum step size $\\sigma$ increased, and in several tests dropped by more than a factor of 12 relative to HSCG.","The total number of inner iterations needed by the improved algorithm stayed roughly constant as $\\sigma$ grew, so choosing $\\sigma$ too large no longer inflates the iteration count.","The heuristic choice of $c_k$ in the previous algorithm is replaced by an automatic estimate, removing one user-supplied parameter and the need for a priori spectral information.","Newton and Chebyshev bases both produced improved convergence behavior, but the paper does not claim either basis is uniformly better; the choice remains problem-dependent."],"supporting_citations":[{"why":"Supplies the incremental norm-estimation algorithms for the extreme Ritz values and the bound underlying equation (4.6).","marker":"[33]"},{"why":"Introduces the previous adaptive s-step CG algorithm that this paper improves and the condition-number-based inner-loop criterion.","marker":"[9]"},{"why":"Provides the rounding-error analysis that bounds the s-step residual gap in terms of the basis condition number.","marker":"[6]"},{"why":"Supplies the sparse test matrices used in the numerical experiments.","marker":"[11]"},{"why":"Gives the Ritz-value-based construction of Newton and Chebyshev basis parameters for Krylov subspaces.","marker":"[34]"},{"why":"Provides the simplified Chebyshev polynomial parameter choice used in equation (2.8).","marker":"[29]"},{"why":"Establishes the exponential growth of the monomial basis condition number, motivating better-conditioned bases.","marker":"[18]"},{"why":"Shows how the s-step basis can be built with O(1) messages per processor, grounding the synchronization-reduction claim.","marker":"[14]"}],"fun_headline_variants":["Dynamic Ritz updates sharpen s-step CG bases, cut syncs","Ritz estimates auto-tune s-step CG bases, fewer syncs","s-step CG with on-the-fly basis updates syncs less","Adaptive bases from Ritz values reduce synchronization cost","Dynamic Ritz-based basis rebuilding cuts s-step CG syncs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the incremental Ritz-value estimates stay accurate enough in finite-precision s-step arithmetic that $\\widetilde{\\lambda}_{\\min}$ never overestimates the true smallest eigenvalue, because equation (4.6) treats $\\widetilde{\\lambda}_{\\min}$ as a lower bound when setting the stopping constant.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic Ritz updates sharpen s-step CG bases, cut syncs","Ritz estimates auto-tune s-step CG bases, fewer syncs","s-step CG with on-the-fly basis updates syncs less","Adaptive bases from Ritz values reduce synchronization cost","Dynamic Ritz-based basis rebuilding cuts s-step CG syncs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000346,"raw_usage":{"total_tokens":1924,"prompt_tokens":1003,"completion_tokens":921,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":833}},"tokens_in":619,"tokens_out":921,"duration_ms":7437,"temperature":1.0,"reasoning_tokens":833,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:51:58.405624+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small symmetric positive definite matrix with an isolated smallest eigenvalue, record $\\widetilde{\\lambda}_{\\min}$ from Algorithm 4 at every inner iteration before convergence and compare it with the true $\\lambda_{\\min}(A)$ from a high-precision eigensolver. If $\\widetilde{\\lambda}_{\\min} > \\lambda_{\\min}(A)$ at any such iteration, the premise behind the bound (4.6) is violated; one can then check whether the residual gap exceeds the bound (2.10) or the algorithm fails to reach the requested tolerance while standard CG succeeds.","supporting_citations":[{"cited_title":"Meurant and P","cited_arxiv_id":null,"evidence_quote":"Supplies the incremental norm-estimation algorithms for the extreme Ritz values and the bound underlying equation (4.6)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the previous adaptive s-step CG algorithm that this paper improves and the condition-number-based inner-loop criterion."},{"cited_title":"Carson and J","cited_arxiv_id":null,"evidence_quote":"Provides the rounding-error analysis that bounds the s-step residual gap in terms of the basis condition number."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sparse test matrices used in the numerical experiments."},{"cited_title":"Philippe and L","cited_arxiv_id":null,"evidence_quote":"Gives the Ritz-value-based construction of Newton and Chebyshev basis parameters for Krylov subspaces."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the simplified Chebyshev polynomial parameter choice used in equation (2.8)."},{"cited_title":"Gautschi, The condition of polynomials in power form , Math","cited_arxiv_id":null,"evidence_quote":"Establishes the exponential growth of the monomial basis condition number, motivating better-conditioned bases."},{"cited_title":"Demmel, M","cited_arxiv_id":null,"evidence_quote":"Shows how the s-step basis can be built with O(1) messages per processor, grounding the synchronization-reduction claim."}],"review_version":1}