{"id":"e68ee041-d9e7-4e89-a37e-d071196ca148","arxiv_id":"2510.11379","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"PCG is proved to reach O(u)-level backward error without the usual tiny-recursive-residual assumption, enabling low-precision preconditioners; a new split PCG variant avoids a known low-precision accuracy loss.","lead":"Conjugate-gradient solvers are shown to reach near-machine-precision backward error without assuming the internal residual becomes unrepresentably small, provided certain iteration-count conditions hold. The proof supports using low-precision preconditioners safely and introduces a split-preconditioned variant that avoids a known accuracy loss.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Condition (76) is not proven to hold for the k* whose existence Lemma 5 asserts; for ill-conditioned A the first small function-value decrease occurs after the (76) threshold, so Theorem 2's central O(u) guarantee is conditional on an unverified existential bound.","rationale":"The reader's weakest assumption identifies exactly the load-bearing concern: condition (76) is a self-referential constraint on the iteration k* whose existence Lemma 5 asserts, and the paper does not prove that any k* can satisfy both the small-function-value requirement and (76). My stress test confirms this is the central gap. The theorem's conclusion—relative backward and forward errors at O(n(k*)^2 u)—only follows for a k* satisfying (76), and the assumptions on A, M, u do not guarantee such a k*. In fact, for a sufficiently ill-conditioned SPD matrix the earliest k* with a function-value drop of order u^2 is ~ sqrt(kappa) log(1/u), while (76) imposes k* ~ 1/(n u kappa); for large kappa the latter is smaller, so no admissible k* exists. This is not merely a technical nuisance: it directly undermines the abstract's claim that PCG can reach O(u) accuracy unconditionally 'after a sufficient number of iterations.' The paper's own conclusions acknowledge the condition ('provided that a certain moderate assumption on the specific iteration k* is met'), but the abstract and framing overstate the result. The numerical experiments are valuable and the derivation appears internally coherent, but they do not fill the existential gap. Since the reader's conditional verdict already captures this, I recommend no change to the verdict: the paper should be accepted only if the authors either prove existence of an admissible k* under stated hypotheses or explicitly frame the abstract's claim as conditional on (76).","tokens_in":34368,"tokens_out":6603,"duration_ms":56938,"concrete_test":"Compute, in exact arithmetic, Algorithm 2 with M = I and the diagonal test matrix (104) with n = 85, lambda_1 = 1, lambda_n = 10^8, rho = 0.6, u = 2^-53. Find the smallest k* satisfying f(bar x_k*) - f(bar x_k*+1) <= n^2 (k*)^2 u^2 ||A||^2 ||x||^2 alpha_k* (taking the paper's O(.) constants to be, say, 1) and evaluate the left-hand side of (76). If (76) fails for this k*, and hence for all larger k* (because the left-hand side is increasing in k*), then Theorem 2 is vacuous for a standard SPD problem, confirming that existence of an admissible k* is an unproven assumption rather than a consequence of the stated hypotheses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5 proves, by monotone boundedness of f(bar x_k), that for any epsilon > 0 there is some k* with f(bar x_k*) - f(bar x_k*+1) <= epsilon (k*)^2 alpha_k*, but it gives no quantitative handle on k*. Theorem 2 then requires that this same k* satisfy (76). The hypotheses on A, M, u do not imply that any such k* exists. For M = I the dominant terms of (76) are O(n k* u kappa(A)) and O((k*)^2 u sqrt(kappa(A))); hence k* must be bounded by roughly 1/(n u kappa(A)). In exact arithmetic, the first index at which the CG function-value drop falls to O(n^2 k^2 u^2)||A||^2||x||^2 alpha_k is at least c sqrt(kappa(A)) log(1/u). For kappa(A) much larger than 1/(n u), this earliest admissible index exceeds the (76) threshold, so no admissible k* exists. The paper's own experiments (Figure 4) show bfloat16 convergence even when the analogous condition (99) fails for all k, confirming the condition is not necessary but also underscoring that the theorem does not cover those convergent runs. The abstract's unconditional 'O(u)' claim is therefore not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a finite-precision analysis of a unified preconditioned conjugate gradient (PCG) framework (Algorithm 2) covering left, right, and split preconditioning. The analysis derives local rounding-error bounds (Lemmas 1–3), a relation between the quadratic objective decrease and the M^{-1}-norm of the recursively updated residual (Lemma 4), an existence statement for an iteration with arbitrarily small objective decrease (Lemma 5), and a quadratic-inequality argument yielding a bound on the residual at that iteration (Lemma 6). The main result, Theorem 2, claims that under O(nu)κ(A)+2ε_pre≤1/2 and condition (76), there is i≤k* such that the true residual and A-norm error satisfy O(n(k*)^2u)κ(M^{-1})^{1/2}-type bounds. The paper also derives precision conditions for Cholesky-factor preconditioners (Lemma 7, Corollary 1) and reports numerical experiments, including comparisons with Saad's split PCG variant.","tokens_in":34640,"tokens_out":6212,"duration_ms":57286,"significance":"If Theorem 2 were unconditional, it would be a significant advance: it would give backward and forward error bounds for PCG at levels O(u) and O(u)κ(A)^{1/2} without the customary assumption that the recursively updated residual norm decreases below machine precision, and it would provide a theoretical basis for applying preconditioners in low precision. The proof is carefully structured, the individual lemmas are clearly stated, no fitted parameters enter the derivation, and the numerical experiments are supported by a publicly available Julia package. However, the central result is conditional on the existence of an iteration k* satisfying (76), and the paper does not prove that such an iteration exists under the stated assumptions. Since the experiments themselves show convergence of bfloat16 cases in which the analogous assumption (99) fails for every k, the scope of the theorem is substantially narrower than the abstract suggests. The contribution is valuable as a framework and as a conditional analysis, but the advertised unconditional claim is not established.","major_comments":[{"comment":"Theorem 2's O(n(k*)²u) bounds require the k* from Lemma 5 to satisfy condition (76), but Lemma 5 only proves the existence of a k* with f(bar x_k*)−f(bar x_{k*+1}) ≤ ε(k*)² αhat_k* together with (66); it gives no quantitative control on k*. The hypotheses O(nu)κ(A)+2ε_pre≤1/2 do not imply that any such k* satisfies (76). For M=I, (76) requires k* ≲ 1/(n u κ(A)), while the first sufficiently small CG objective decrease in exact arithmetic can occur at k* of order sqrt(κ(A)) log(1/u); for κ(A) ≫ 1/(nu) these regimes are disjoint. Thus the paper's central 'O(u)' claim is only conditional on an unverified existential bound. Please either prove that such a k* exists or state (76) as an explicit assumption in Theorem 2 and revise the abstract/conclusions accordingly. The current wording 'there exists k* ... if k* satisfies (76)' does not authorize the abstract's unconditional reading.","section":"§4.3, Lemmas 5–6 and Theorem 2"},{"comment":"The advertised improvement of Algorithm 2 over Saad's split PCG (Section 3 and Figure 2) is attributed to a claimed O(u+u_L) limitation of Saad's variant, but footnote 4 says the derivation is omitted. This claim is load-bearing for the paper's comparative conclusion. Without a proof, the comparison is only an empirical observation. Please include the derivation or explicitly state that the O(u+u_L) bound is a heuristic supported only by the experiments.","section":"§5, footnote 4"},{"comment":"The bfloat16 experiments converge even though the corresponding assumption (99) fails for every k≥1. The text mentions this, but it is not just a harmless observation: it shows that the theorem's hypotheses are not necessary and, more importantly, that the converged bfloat16 runs are not covered by Theorem 2. The manuscript should clearly state that these numerical results are outside the theorem's scope and explain what the experiments are intended to demonstrate—e.g., the sufficiency, but not necessity, of the conditions, or the practical looseness of the bounds.","section":"§5, Figures 1/4 and Corollary 1"}],"minor_comments":[{"comment":"The abstract's O(u) and O(u)κ(A)^{1/2} wording suppresses the factors n(k*)², κ(M^{-1})^{1/2}, and max_{j≤k*+1}(||xhat_j||/||x||,1). Please state the full scaling in the abstract or add a sentence making clear that 'O(u)' here depends polynomially on n and k*.","section":"Abstract and Theorem 2"},{"comment":"The keyword 'conjugated gradient algorithm' should be 'conjugate gradient algorithm'.","section":"Keywords"},{"comment":"The caption says 'first row' and 'second row', but the figure shows three separate heatmaps (a), (b), (c). Please correct the caption to match the actual layout.","section":"Figure 3 caption"}],"recommendation":"major_revision","confidential_remarks":"The main gap is the unproved existence of a k* satisfying condition (76). If the authors can prove such existence under reasonable conditions, the paper would be a strong contribution. If not, the claims must be substantially weakened to an explicit conditional theorem. I lean toward major revision rather than rejection because the framework and lemmas are carefully developed and could support a corrected version, but the current abstract and Section 6 overstate what is rigorously established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading. It gives the first PCG error bounds that do not assume the recursively updated residual drops below machine precision, and the proof is mostly careful and coherent. The optimization-based quadratic inequality argument is a real departure from Greenbaum, Gutknecht–Strakos, and Strakoš–Tichý. Theorem 2's bounds at O(n(k*)^2 u) with the kappa(M^{-1})^{1/2} factors are derived with attention to detail; Lemmas 1–6 hang together, the Cholesky preconditioner error models are standard, and the unified Algorithm 2 with the new split variant is a useful practical contribution. The code is available and the experiments support the qualitative claims.\n\nThe main soft spot is exactly what the report flags. Lemma 5 produces some k* where the function-value drop is tiny, but nothing guarantees that this same k* satisfies condition (76). For moderately ill-conditioned problems (n=85, kappa=1e5) the condition is trivially met, but for larger kappa(A) the inequality forces k* to be at most roughly 1/(n u kappa(A)), while the first small function-value drop appears only after about sqrt(kappa(A)) log(1/u) iterations. For ill-conditioned enough matrices those ranges do not overlap, so Theorem 2 is conditional on an unverified existential. The abstract's \"O(u)\" wording hides the n(k*)^2 factor and the condition entirely. The paper's own bfloat16 experiments converge even when condition (99) fails, which is fine, but it underscores that the theorem does not cover those convergent runs. Footnote 4 omits the derivation for the Saad split-PCG comparison, a minor but real gap.\n\nThis is a paper for specialists in finite-precision Krylov methods and mixed-precision linear algebra. It deserves a serious referee: the core result is new and largely correct, but the authors should either prove that an admissible k* exists under the stated assumptions, or make the abstract explicitly conditional. I would ask for revision, not desk rejection. Send it to peer review.","headline":"Genuinely new result with a real conditional gap: the proof removes the residual-smallness assumption, but the abstract's O(u) claim overstates Theorem 2's dependence on an unverified k* satisfying condition (76).","tokens_in":35211,"tokens_out":5288,"would_cite":true,"duration_ms":45581,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","65F08","65G50","65Y20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The preconditioned conjugate gradient algorithm can reach backward error O(u) and forward error O(u)√κ(A) without assuming the recursive residual norm drops below machine precision.","keywords":["conjugate gradient","preconditioning","mixed precision","backward error","forward error","rounding error analysis","finite precision","Krylov subspace methods"],"falsifier":"Run PCG (with M=I for simplicity) on an SPD matrix whose eigenvalues are clustered so that the CG polynomial decreases slowly, e.g., n=100, condition number 10^8, with eigenvalues packed near the extremes; track the actual quadratic difference f(x̄_{k+1})−f(x̄_k) in floating point. Find the smallest k where this difference falls below O(n²k²u²)‖A‖²‖x‖²; if that k also satisfies n k u κ(A) > 1/2 (so condition (76) fails), then check whether the relative backward error at that iterate is indeed larger than the bound O(n k² u) max(‖x̂_j‖/‖x‖). If the backward error remains O(u) anyway, the theore","tokens_in":34156,"feed_emoji":"🧮","tokens_out":6988,"duration_ms":53073,"temperature":0.7,"pith_summary":"This paper proves that the preconditioned conjugate gradient (PCG) algorithm, when run in finite precision, can reach relative backward error on the order of the machine roundoff unit u and relative forward error on the order of u times the square root of the condition number of the matrix A — and it does so without the usual assumption that the recursively updated residual norm falls far below u. Previous analyses of CG-type methods took that small-recursive-residual condition as a starting point and then bounded the residual gap; this work instead uses the fact that CG minimizes a quadratic function, showing that the difference in function values at two consecutive iterates eventually becomes tiny. From that, the authors derive a quadratic inequality whose solution bounds the residual, and hence the backward and forward errors. They also show that applying preconditioners in reduced precision does not degrade these accuracy levels under stated conditions, and they introduce a split-preconditioned variant that avoids the accuracy loss that occurs when the left preconditioner is applied in low precision in the classical split algorithm.","feed_headline":"PCG backward error reaches O(u) with no residual-gap assumption","feed_subtitle":"A quadratic-function argument replaces the old assumption that recursive residuals must drop below machine precision.","key_machinery":"The load-bearing object is the quadratic objective f(y)=½yᵀAy−yᵀb of the linear system, together with the specific iteration index k* at which the difference f(x̄_{k*)})−f(x̄_{k*+1}) first becomes as small as O(n²(k*)²u²). Lemma 4 expresses this difference as −½α̂_k(1+δα̂_k)‖r̂_k‖²_{M^{-1}} plus a perturbation; Lemma 5 proves such a k* exists because the monotone sequence f(x̄_k) converges; Lemma 6 combines these into a quadratic inequality in ‖r̂_k‖_{M^{-1}} and solves it. The standard residual-gap bound (Theorem 1) is then used only after the recursive residual is already known to be small, not as an assumption.","core_discovery":"The central result is Theorem 2: under the assumption that O(nu)κ(A)+2ε_pre ≤ 1/2 and that the specific iteration k* whose existence is guaranteed by Lemma 5 also satisfies condition (76), there is an index i ≤ k* for which the relative true-residual (backward) error satisfies ‖b−Ax̂_i‖/(‖A‖‖x‖) ≤ O(n(k*)²u) κ(M^{-1})^{1/2} max_{j≤k*+1}(‖x̂_j‖/‖x‖,1), the same bound holds for the recursively updated residual, and the A-norm forward error satisfies ‖x̂_i−x‖_A/(‖A‖^{1/2}‖x‖) ≤ O(n(k*)²u) κ(M^{-1})^{1/2} κ(A)^{1/2} max(...). These are the first bounds in this literature that reach the levels O(u) and O(u)κ(A)^{1/2} without assuming the recursively updated residual norm has already dropped below","pith_inferences":["The monotone-convergence argument suggests a practical stopping rule: monitor f(x̄_{k+1})−f(x̄_k) and stop when it drops below a threshold proportional to n²u²‖A‖²‖M^{-1}‖‖x‖²; this would directly trigger the regime where Theorem 2's bounds hold, and is implementable without forming the true residual.","Because condition (76) bounds k* in terms of n, u, κ(A), and κ(M), the analysis implies a trade-off between allowed iterations and the working precision: for a fixed precision, there is an effective maximum number of PCG iterations beyond which the theorem no longer guarantees accuracy. A testable extension is to construct an SPD system where the optimal CG polynomial converges so slowly that the ","The same optimization-based proof strategy might extend to other iterative solvers with a variational formulation, such as symmetric indefinite MINRES, where analogous residual-gap assumptions are currently used."],"forward_implications":["For any SPD system satisfying the stated conditions, PCG is provably backward stable in the O(u) sense and forward stable in the O(u)κ(A)^{1/2} sense; no separate assumption about the recursive residual norm is needed.","Preconditioners can be stored and applied in lower precision than the working precision without changing the asymptotic error bounds, as long as the precision-dependent parameters ε_s, ε_q, ε_z keep condition (99) satisfied; Corollary 1 gives explicit thresholds for Cholesky-factor preconditioners.","The split-preconditioned variant of Algorithm 2 does not suffer the accuracy degradation seen in the classical split PCG when the left preconditioner is applied in low precision, because the left-preconditioner solve is not embedded in the residual recurrence.","The bounds degrade polynomially with n and k*, so the theorem predicts that very slow convergence can eventually destroy the O(u) guarantee; the authors observe that in practice no failure is seen when the initial guess has a normal size."],"fun_headline_variants":["PCG error bounds without the residual-gap assumption","Mixed-precision PCG: O(u) accuracy, no residual-drop required","New PCG proof: O(u) backward, O(u)√κ forward, no residual crutch","Low-precision preconditioners don't hurt PCG accuracy","First PCG bounds skipping residual-below-machine-precision assumption"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof needs the first iteration at which the quadratic function values stop changing to occur before the accumulated rounding error terms O(n k* u) grow past 1/2; Lemma 5 shows such an iteration exists but does not bound how early it happens.","fun_headline_variants_meta":{"raw":{"variants":["PCG error bounds without the residual-gap assumption","Mixed-precision PCG: O(u) accuracy, no residual-drop required","New PCG proof: O(u) backward, O(u)√κ forward, no residual crutch","Low-precision preconditioners don't hurt PCG accuracy","First PCG bounds skipping residual-below-machine-precision assumption"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000646,"raw_usage":{"total_tokens":2852,"prompt_tokens":840,"completion_tokens":2012,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":584,"completion_tokens_details":{"reasoning_tokens":1917}},"tokens_in":584,"tokens_out":2012,"duration_ms":12380,"temperature":1.0,"reasoning_tokens":1917,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T10:08:44.275486+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PCG (with M=I for simplicity) on an SPD matrix whose eigenvalues are clustered so that the CG polynomial decreases slowly, e.g., n=100, condition number 10^8, with eigenvalues packed near the extremes; track the actual quadratic difference f(x̄_{k+1})−f(x̄_k) in floating point. Find the smallest k where this difference falls below O(n²k²u²)‖A‖²‖x‖²; if that k also satisfies n k u κ(A) > 1/2 (so condition (76) fails), then check whether the relative backward error at that iterate is indeed larger than the bound O(n k² u) max(‖x̂_j‖/‖x‖). If the backward error remains O(u) anyway, the theore","supporting_citations":[],"review_version":1}