{"id":"f9be0253-3687-42c1-808c-f9343bcbd59a","arxiv_id":"2509.07305","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Block LU backward error is bounded quadratically in a new blockwise growth factor, and BEAM provably needs no modifications for diagonally dominant, H-matrix, and SPD inputs.","lead":"This paper tightens the stability theory for block LU factorization, the engine behind the communication-efficient BEAM solver, cutting the known error bound from cubic to quadratic dependence on element growth. It also shows when the BEAM algorithm can skip its singular-value modifications without hurting stability.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Clamped-SVD step is not shown to satisfy (2.4)-(2.7); applying the quadratic bound to BEAM requires either a backward-stability proof for this step or a clear re-targeting of the bound to the modified matrix.","rationale":"The core block-LU theorem is a conditional statement: if the block operations satisfy the normwise error model (2.4)-(2.7), then the backward error is bounded quadratically in the block growth factor. The proof is internally consistent, and the improvement over the cubic bound is genuine. The weak spot is the transfer to BEAM. The SVD-plus-clamping step is not a standard backward-stable factorization of the input diagonal block; it deliberately modifies the matrix. Therefore Theorem 2.3 can only apply to the modified matrix eA, and the subsequent use of kappa(A) and P(A) in Table 2.1 and in the reader's strongest claim requires an additional argument bounding kappa(eA) in terms of kappa(A) and tauhat. Section 3 does not supply such a bound in general. This is a real limitation but not a contradiction: the paper's formal theorems for block LU stand, and the BEAM-specific claim is best read as conditional on the clamped-SVD factorization being backward stable relative to eA and on a clarification of which matrix the bounds use. Hence the reader's ACCEPT verdict remains appropriate, with the same moderate confidence.","tokens_in":18111,"tokens_out":37180,"duration_ms":445085,"concrete_test":"Implement Algorithm 1.1's diagonal step in double precision for A_kk = diag(1e-12,1) with tauhat=1e-8. Check (i) whether ||A_kk - Uhat Sigma_clamped Vhat^T||_2 / (u||A_kk||_2) is O(1); if it is much larger, (2.4) fails for the unmodified block. Then, for a range of random matrices with small singular values, compute kappa(eA) and compare it with min(kappa(A), tauhat^-1). If kappa(eA) exceeds the claimed bound, Table 2.1's BEAM row and the associated quadratic bound for BEAM are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2.3's quadratic backward-error bound rests entirely on assumptions (2.4)-(2.7). In BEAM (Algorithm 1.1, lines 6-13), the diagonal-block 'factorization' is an SVD followed by clamping singular values below tau to tau. For a diagonal block whose unmodified singular value sigma_i <= tau, the computed product U Sigma_clamped V^T differs from the input block by (tau-sigma_i)u_i v_i^T, an O(tau)=O(tauhat||A||) perturbation, not O(u)||A_kk||. Thus (2.4) cannot hold for the unmodified Schur-complement block. The paper's escape is to say BEAM factors the modified matrix eA (Sec. 1.1); but then Theorems 2.6/2.7 and Table 2.1 must use P(eA), kappa(eA), and ||eA||. The paper does not prove kappa(eA) <= min(kappa(A), tauhat^-1); Section 3 gives only exponential or conditional bounds for kappa(eA). So the headline 'quadratic-in-growth bound for BEAM' is not established: it is either applied to the wrong matrix or missing a backward-stability lemma for the clamped-SVD operation. The block-LU theorem itself is internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the numerical stability of block LU factorization and of the BEAM algorithm, which replaces pivoting by additive modifications of small singular values in the diagonal blocks. It defines a block-aligned growth factor P^I_α, proves a backward error bound for block LU that is quadratic in this growth factor rather than cubic in the pointwise growth factor (Theorems 2.3 and 2.6), and applies the framework to several matrix classes (diagonally dominant, block diagonally dominant, SPD). In the second half it analyzes the effect of BEAM's additive modifications on the condition number and growth of the modified matrix, gives an exponential bound for the general case, studies the Zielke matrix as a worst-case example, and provides sufficient conditions, based on diagonal dominance, H-matrix properties, and SPD structure, under which BEAM makes no modifications.","tokens_in":18393,"tokens_out":19508,"duration_ms":218690,"significance":"The block LU result is a genuine theoretical improvement: it is not limited to the standard formulation with identity diagonal blocks of L, it replaces a cubic dependence on the pointwise growth factor with a quadratic dependence on a block-adapted growth factor, and it applies to matrices for which pointwise LU may not even exist, such as a matrix with leading block [0 1; 1 0]. The paper is careful in stating assumptions (2.4)-(2.7) with explicit constants, and it is transparent about limitations, notably that the general bound on the inverse of the modified matrix is exponential. If the BEAM-specific claims are properly qualified, the analysis is a useful contribution to the numerical stability literature.","major_comments":[{"comment":"For BEAM, the matrix actually factored is eA = A + M_U M_Σ M_V^T, as stated in §1.1. Applying Theorem 2.6 to eA replaces P, κ, and ||A|| by P(eA), κ(eA), and ||eA||. The paper does not prove κ(eA) ≤ min(κ(A), τ̂^-1) nor P(eA) ≤ C P(A); Section 3 leaves the general bound on ψ = ||eA^{-1}||/||A^{-1}|| exponential in n (Thm. 3.2). Therefore the Table 2.1 row “BEAM modified (P^I)^2 min(κ(A), τ̂^-1)” is not supported. Either prove the required bounds for eA or state the BEAM row as conditional on the growth and condition of eA.","section":"§2.4, Table 2.1, Thms. 2.6–2.7"},{"comment":"For the clamped-SVD diagonal factorization, the unmodified singular value σ_i ≤ τ is replaced by τ, so U_k Σ_clamped V_k^T differs from the input diagonal block by (τ−σ_i) u_i v_i^T, an O(τ) perturbation rather than O(u)||A_kk||. The paper's escape is that BEAM factors the modified matrix eA, but this transfer is implicit. Please state and prove a backward-stability lemma: with eA defined using the computed SVD factors and clamped values, (2.4) holds for eA with an error of order u||A_kk||. Also clarify that the quantities A^(k) in Theorem 2.3 are exact Schur complements; applying the theorem to a recursion on computed Schur complements requires an additional accumulation argument.","section":"§2.2, eqs. (2.4)–(2.7), Algorithm 1.1 lines 6–13"},{"comment":"The display “P_α ≤ 1 + max_k || eA^{-1}_{1:k,1:k} ||_α ||A||_α” uses the original matrix norm ||A||_α, whereas the analogue of (2.3) for the matrix eA being factored must use ||eA||_α. As written this is not a consequence of Theorem 2.2 and it obscures which matrix the growth factor P refers to. This is not a pure typo because it feeds into the overclaim about the BEAM row in Table 2.1.","section":"§3, second paragraph"}],"minor_comments":[{"comment":"“we analyzed the modifications” should be “we analyze” to match the tense of the rest of the abstract.","section":"Abstract"},{"comment":"The summation limits in the first displayed bound after “Continuing the iteration” are swapped relative to the theorem statement: c_L1 should run to n_t and c_L2 to n_t−1. The theorem statement has the correct limits.","section":"§2.2, Theorem 2.4 proof"},{"comment":"“A(k) independent of how the diagonal blocks are factored” is missing a verb; should be “A(k) is independent”.","section":"§2.3"},{"comment":"The sentence “all by the last row” should be “all but the last row”.","section":"§3, after Thm. 3.2"},{"comment":"The proof uses implicitly that (A^(k))^{-1} is a trailing principal submatrix of A^{-1}, so that ||(A^(k))^{-1}||_p ≤ ||A^{-1}||_p. This should be stated, since it is the key step relating the L-factor to κ_p(A).","section":"§2.6 (Theorem 2.6 proof)"}],"recommendation":"major_revision","confidential_remarks":"The block-LU theorem itself is solid and likely publishable, but the BEAM-related claims in Table 2.1 and in the surrounding discussion need to be either proved with respect to the modified matrix eA or explicitly marked as conditional. The footnote discloses substantial overlap of Sections 2.1–2.2 with the first author's dissertation; the editor may want to evaluate the journal's policy on prior dissertation publication. There are no inappropriate citations or fitted parameters; the analysis is clean and reproducible in principle."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a genuinely useful paper. The main contribution—replacing the cubic-in-pointwise-growth bound for block LU with a quadratic bound in a block-aligned growth factor—is real and cleanly proven. Theorem 2.6, with unitary diagonal blocks of L, is a nice step forward, and the block growth factor P^I is a sensible definition that also covers matrices pointwise LU cannot factor, like the [0 1; 1 0] leading block example. Section 4's no-modification criteria for H-matrices and SPD matrices are practical and well argued. I also appreciate the explicit disclosure that parts of Section 2 appeared in the dissertation; that is not a problem for me.\n\nThe soft spot is exactly where the reader's weakest assumption sits, and the stress-test note sharpens it: the clamped-SVD step in BEAM is not a backward-stable factorization of the original diagonal block. If a singular value is below tau, the computed product differs from the input block by O(tau), so assumption (2.4) cannot hold for the unmodified A_kk. The paper's escape—Algorithm 1.1 factors the modified matrix tilde-A—is the right move, but then every bound that feeds into a statement about BEAM must use tilde-A's growth factor, condition number, and norm. The paper does not always do this. Theorem 2.7 is stated for a matrix whose diagonal blocks have small singular values bounded below, which is fine for tilde-A, but Table 2.1's 'BEAM modified' row writes min(kappa(A), tauhat^-1), mixing A and tilde-A. Section 3 gives only exponential or conditional bounds on kappa(tilde-A), so the table entry is not justified as stated. This is a real gap, but it is fixable and not fatal: the core block-LU theorem is internally consistent, and the paper honestly says it is analyzing the underlying factorization and the modifications separately.\n\nI would not desk-reject this. The referee should ask the authors to make the target matrix explicit in every theorem that is advertised as a BEAM bound, and to either prove a usable bound on kappa(tilde-A) or tone down the table claim. The math is worth engaging. Who benefits: dense NLA researchers working on communication-avoiding LU and anyone trying to understand when modification-based solvers can be trusted. I would take it to a reading group if the group does stability analysis, and I would cite the quadratic block-LU bound in my own work. Send it to peer review.","headline":"Solid improvement of the Demmel-Higham-Schreiber stability bound for block LU; the BEAM transfer is not as clean as the headline claims, but the core theorem holds.","tokens_in":18896,"tokens_out":5318,"would_cite":true,"duration_ms":63488,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A23","65F05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Block LU factorization, as used in the BEAM solver, has backward error bounded by the square of a block-aligned growth factor rather than the cube of the pointwise growth factor, extending stability analysis to matrices that pointwise LU ca","keywords":["block LU factorization","growth factor","backward error analysis","BEAM","additive modifications","Gaussian elimination","singular value decomposition","condition number"],"falsifier":"Compute BEAM's backward error ||A - Lhat Rhat||_2 on a matrix with moderate blockwise growth but with a diagonal block whose smallest singular value sits just below tau and whose singular vectors interact badly with the trailing update; if the per-unit-roundoff error grows faster than P^2 as the block count increases, the quadratic bound does not transfer to the implemented clamped-SVD step.","tokens_in":17987,"feed_emoji":"🧮","tokens_out":11418,"duration_ms":119987,"temperature":0.7,"pith_summary":"This paper proves that block LU factorization is more stable than previous analyses indicated: its backward error grows at most quadratically in a block-aligned growth factor, not cubically in Wilkinson's classic pointwise growth factor. The improvement matters because block LU is the core of the BEAM solver, a communication-avoiding alternative to LU with partial pivoting, and the new measure lets the theory cover matrices for which ordinary pointwise LU does not even exist, such as a matrix whose leading 2x2 block is [0 1; 1 0]. The proof route is a general backward-error theorem for block LU combined with a norm bound for the computed L and R factors when the diagonal blocks of L are unitary, which is exactly the SVD-based situation in BEAM. The paper separately analyzes BEAM's additive modifications, bounding how far they can inflate the condition number and showing that Zielke's matrix still produces exponential growth. It closes with simple thresholds, based on diagonal dominance and related quantities, under which BEAM applies no modifications at all, so the behavior of ordinary block LU is preserved.","feed_headline":"Block LU stability: growth cost drops from cubic to quadratic","feed_subtitle":"New block-aligned growth factor covers matrices where standard LU fails, including BEAM's SVD-based solver.","key_machinery":"The central object is the block-aligned growth factor P^I_alpha, defined as the maximum over elimination steps of the norm of the current Schur complement divided by the norm of the original matrix; it replaces Wilkinson's pointwise growth factor and is independent of how diagonal blocks are factored. The second main ingredient is the blockwise backward-error Theorem 2.3, which reduces the error of the whole factorization to assumed normwise errors of each block operation. Theorem 2.6 then bounds ||L|| ||R|| in Schatten p-norms when diagonal blocks of L are unitary, using the Schur-complement identity for subdiagonal blocks of L; the product is O(n_t^2 P_p^2 kappa_p(A) ||A||), which is what","core_discovery":"The paper's central claim is that the backward error of block LU is controlled by a blockwise growth factor P^I_alpha = max_k ||A^(k)||_alpha / ||A||_alpha over the Schur complements produced during elimination, and that when the diagonal blocks of L are unitary (as they are in BEAM), the bound becomes O(u P^I ||A||) + O(u n_t^2 (P^I)^2 kappa(A) ||A||) up to polynomial factors. This is quadratic in the blockwise growth factor, improving on the previous cubic-in-pointwise-growth bound, and it applies to matrices whose pointwise LU factorization is undefined. The argument proceeds by first proving a general backward-error theorem for Algorithm 2.1 under per-block normwise assumptions, then bou","pith_inferences":["Because the growth factor P^I_alpha is defined on Schur complements that are already computed, it could be monitored cheaply at runtime and used to decide when to switch from BEAM to a pivoting strategy.","A direct rounding-error analysis of the clamped-SVD diagonal-block factorization would settle whether the assumed bound (2.4) holds with moderate constants; until then, the quadratic bound applies to BEAM's formulation conditional on that backward stability.","The Zielke example suggests that additive modifications alone cannot eliminate worst-case growth, so a practical BEAM variant might combine SVD clamping with block-dependent pivot selection, as hinted by the diagonal-block pivoting strategy noted in the paper.","The modification-free criteria for H-matrices could be deployed as a cheap precheck that skips Woodbury correction and iterative refinement entirely for matrices whose diagonal dominance factors are large enough."],"forward_implications":["A backward error that scales like (P^I)^2 instead of (P^I)^3 means BEAM and other block LU implementations can tolerate substantially larger element growth before the solution is polluted by roundoff.","Matrices that pointwise LU cannot factor, such as those with a leading block [0 1; 1 0], are now covered by a stability guarantee, so the blockwise analysis broadens the class of matrices for which pivotless block elimination is justified.","For block diagonally dominant matrices and inverses of row-block-diagonally dominant matrices, the combined bounds give backward error constants independent of the condition number, matching the best known pointwise results without pivoting.","If tau-hat kappa_2(A) is at most 0.5, BEAM's modifications change the inverse by at most a factor of 2, so the Woodbury-based correction step is provably stable for moderately conditioned or mildly modified systems.","For diagonally dominant, H-, symmetric positive definite, and block diagonally dominant matrices, BEAM takes the modification-free path for sufficiently small tau, making the extra Woodbury work unnecessary on those well-behaved classes."],"supporting_citations":[{"why":"Introduces BEAM and its SVD-based diagonal-block factorization with additive modifications and the Woodbury correction; this is the method whose stability is analyzed.","marker":"[14]"},{"why":"Supplies the previous block LU stability analysis with cubic dependence on pointwise growth, which the new quadratic blockwise bound improves.","marker":"[4]"},{"why":"Defines Wilkinson's classic pointwise growth factor and error bounds, used to calibrate and compare the blockwise results.","marker":"[20]"},{"why":"Reference for pointwise LU backward error and stable block operations, used for the comparisons in Section 2.4.","marker":"[11]"},{"why":"Provides an infinity-norm growth factor and backward error analysis for pointwise LU that the blockwise analysis generalizes and compares against.","marker":"[1]"},{"why":"Establishes block LU stability for inverses of block diagonally dominant matrices, supplying the bounds used in Theorem 2.9.","marker":"[10]"},{"why":"Supplies the Schur-complement quotient formula for determinants used to bound inverses of modified leading principal submatrices in Theorem 3.2.","marker":"[22]"},{"why":"Defines Zielke's test matrices, used in Theorem 3.3 to show that modifications can still lead to exponential growth.","marker":"[23]"},{"why":"Provides Varah's lower bound on the smallest singular value used in Section 4's modification-free criteria for diagonally dominant and block diagonally dominant matrices.","marker":"[17]"},{"why":"Supplies the Woodbury formula for the inverse of a modified matrix, which carries the capacitance-matrix condition-number analysis in Theorem 3.1.","marker":"[21]"}],"fun_headline_variants":["Block LU growth bound: cubic to quadratic","Stable block LU with quadratic growth measure","New blockwise growth factor beats LU's limit","Block LU error analysis improved to quadratic"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that every block operation in Algorithm 2.1, including BEAM's SVD factorization of a diagonal block with small singular values clamped to tau, has roundoff error bounded by a small constant times machine precision; the paper assumes this for the clamped-SVD step rather than proving it.","fun_headline_variants_meta":{"raw":{"variants":["Block LU growth bound: cubic to quadratic","Stable block LU with quadratic growth measure","New blockwise growth factor beats LU's limit","Block LU error analysis improved to quadratic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000507,"raw_usage":{"total_tokens":2288,"prompt_tokens":707,"completion_tokens":1581,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":451,"completion_tokens_details":{"reasoning_tokens":1526}},"tokens_in":451,"tokens_out":1581,"duration_ms":13079,"temperature":1.0,"reasoning_tokens":1526,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T22:27:58.526855+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute BEAM's backward error ||A - Lhat Rhat||_2 on a matrix with moderate blockwise growth but with a diagonal block whose smallest singular value sits just below tau and whose singular vectors interact badly with the trailing update; if the per-unit-roundoff error grows faster than P^2 as the block count increases, the quadratic bound does not transfer to the implemented clamped-SVD step.","supporting_citations":[{"cited_title":"Lindquist, P","cited_arxiv_id":null,"evidence_quote":"Introduces BEAM and its SVD-based diagonal-block factorization with additive modifications and the Woodbury correction; this is the method whose stability is analyzed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Wilkinson's classic pointwise growth factor and error bounds, used to calibrate and compare the blockwise results."},{"cited_title":"Amodio and F","cited_arxiv_id":null,"evidence_quote":"Provides an infinity-norm growth factor and backward error analysis for pointwise LU that the blockwise analysis generalizes and compares against."},{"cited_title":"George and Kh","cited_arxiv_id":null,"evidence_quote":"Establishes block LU stability for inverses of block diagonally dominant matrices, supplying the bounds used in Theorem 2.9."},{"cited_title":"Zielke , Testmatrizen mit maximaler Konditionszahl , Computing, 13 (1974), pp","cited_arxiv_id":null,"evidence_quote":"Defines Zielke's test matrices, used in Theorem 3.3 to show that modifications can still lead to exponential growth."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Woodbury formula for the inverse of a modified matrix, which carries the capacitance-matrix condition-number analysis in Theorem 3.1."}],"review_version":1}