{"id":"c5d7ae2e-b431-4c91-90d2-772506e65d2a","arxiv_id":"2605.21679","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Triplet-based versions of cyclic reduction and incremental Newton compute the principal square root of M-matrices with component-wise numerical stability independent of singularity and condition number.","lead":"This paper introduces triplet representations to design component-wise accurate algorithms for the principal square root of M-matrices, adapting cyclic reduction and incremental Newton iterations. A smart generalist might read it because stable matrix square roots matter for reliable simulations in stochastic modeling and numerical PDEs.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Stability proof for adapted iterations may not fully cover rounding error accumulation when the triplet vectors become linearly dependent in the singular case.","rationale":"The reader's weakest assumption (triplet preservation for the square root) is the precise point at which the stability argument must be checked; extending it to finite-precision iteration in the singular regime is the least secure step in the central claim.","tokens_in":1665,"tokens_out":411,"duration_ms":31350,"concrete_test":"Take the family of singular tridiagonal M-matrices A_n = tridiag(-1,2,-1) for n = 2^k, k=3..12 (all have kernel spanned by the all-ones vector). Supply the exact triplet with u = ones(n), v = zeros(n) and P the off-diagonal part. Run the triplet-form Incremental Newton iteration to convergence in double precision; compute the component-wise relative residual max | (X^2 - A)_{ij} | / |A_{ij}| over all entries and verify whether it stays below 100*eps for all n.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper establishes that an M-matrix given by triplet (P, u, v) has a principal square root that also admits a triplet, then rewrites Cyclic Reduction and Incremental Newton to operate directly on the triplet. Component-wise stability independent of singularity and cond(A) is claimed via backward-error or perturbation arguments that exploit positivity and the relation A u = v. However, when A is singular the vector v lies in the range of A and u may lie in the kernel direction; the update formulas for the new triplet (P', u', v') involve divisions or subtractions whose denominators can approach machine epsilon times ||u|| even if the mathematical quantities remain well-defined. The analysis does not appear to supply a uniform bound on the propagated relative perturbation in each entry of the computed square root that remains O(eps) when these denominators shrink.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper defines a triplet representation (P, u, v) for an M-matrix A with u > 0, v ≥ 0 and A u = v. It proves that if A admits such a representation then its principal square root X also admits a triplet representation, and rewrites the Cyclic Reduction and Incremental Newton iterations to operate directly on the triplet. The central claim is that these adapted algorithms are component-wise numerically stable with relative error O(ε) in each entry of the computed square root, independently of whether A is singular and independently of cond(A). Numerical experiments are presented to illustrate the claimed stability.","tokens_in":1865,"tokens_out":632,"duration_ms":30236,"significance":"If the component-wise stability result holds, the work supplies a practical and theoretically grounded method for accurate square-root computation on M-matrices that arise in Markov chains, discretizations of elliptic PDEs, and other applications where matrices are often ill-conditioned or singular. The structure-preserving triplet approach and the independence from conditioning constitute a genuine technical contribution; the explicit adaptation of two standard iterations is a clear strength.","major_comments":[{"comment":"§4 (adapted iterations) and §5 (stability analysis): the update formulas for the new triplet (P', u', v') contain divisions and subtractions whose denominators are entries of u or linear combinations involving u and v. When A is singular, v lies in the range of A and u may approach a kernel direction, so these denominators can be as small as O(ε)‖u‖ while the mathematical quantities remain well-defined. The perturbation argument given does not supply a uniform bound showing that the relative perturbation in each entry of the computed square root remains O(ε) under these conditions.","section":"§5"},{"comment":"Theorem 3.2 (triplet preservation for the square root): the existence proof is algebraic and relies on the positivity properties of M-matrices, but the subsequent numerical-stability claim in §5 is not shown to be independent of the linear dependence that appears between u and v precisely when A is singular. A concrete counter-example or a refined error-propagation estimate that remains valid in the singular limit is needed to support the strongest claim.","section":"Theorem 3.2"}],"minor_comments":[{"comment":"The numerical experiments section would benefit from explicit reporting of the smallest singular values of the test matrices and of the observed relative errors in the singular cases, so that the independence claim can be directly verified from the tables.","section":"Numerical experiments"},{"comment":"Notation: the vectors u and v are sometimes written in bold and sometimes not; consistent boldface throughout would improve readability.","section":"Notation"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a good fit for a numerical-analysis journal. The stability analysis for the singular case is the only load-bearing gap; once addressed, the paper should be publishable."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the detailed and constructive report. The comments highlight important aspects of the stability analysis in the singular case, and we address each point below. We will revise the manuscript to provide a refined error analysis that explicitly treats the singular limit.","responses":[{"response":"We agree that the perturbation argument in §5 needs to be strengthened for the singular case. Although the current analysis relies on positivity and component-wise bounds derived from the M-matrix structure, it does not explicitly derive a uniform relative-error bound when denominators in the triplet updates become small. In the revised manuscript we will add a refined perturbation analysis in §5 that tracks the error propagation through the divisions and subtractions by exploiting the fact that the triplet updates preserve the M-matrix property and that the accumulated rounding errors remain relatively small in each entry. This will establish the O(ε) component-wise bound independently of singularity.","revision_made":"yes","referee_comment":"[§5] §4 (adapted iterations) and §5 (stability analysis): the update formulas for the new triplet (P', u', v') contain divisions and subtractions whose denominators are entries of u or linear combinations involving u and v. When A is singular, v lies in the range of A and u may approach a kernel direction, so these denominators can be as small as O(ε)‖u‖ while the mathematical quantities remain well-defined. The perturbation argument given does not supply a uniform bound showing that the relative perturbation in each entry of the computed square root remains O(ε) under these conditions."},{"response":"Theorem 3.2 is an algebraic existence result that holds for both singular and nonsingular M-matrices; it does not address numerical stability. The stability claim is made for the adapted algorithms and is analyzed in §5. We acknowledge that the present error-propagation argument does not explicitly address the linear dependence between u and v that arises at singularity. In the revision we will supply a refined component-wise error-propagation estimate that remains valid in the singular limit, using the limiting behavior of the triplet updates and the nonnegativity properties of M-matrices. We will also augment the numerical experiments with additional singular and near-singular test cases to illustrate the claimed independence from cond(A).","revision_made":"yes","referee_comment":"[Theorem 3.2] Theorem 3.2 (triplet preservation for the square root): the existence proof is algebraic and relies on the positivity properties of M-matrices, but the subsequent numerical-stability claim in §5 is not shown to be independent of the linear dependence that appears between u and v precisely when A is singular. A concrete counter-example or a refined error-propagation estimate that remains valid in the singular limit is needed to support the strongest claim."}],"tokens_in":1448,"tokens_out":601,"duration_ms":34531,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's main point is that an M-matrix given in triplet form (P, u, v) with A u = v has a principal square root that also admits a triplet, and the authors rewrite the cyclic reduction and incremental Newton iterations to operate directly on that triplet. This produces component-wise accurate results that the abstract says remain stable independent of whether A is singular or how large its condition number is. The experiments are presented as confirmation that the computed entries stay close to the true ones in relative terms even on tough examples from applications like stochastic processes.","headline":"The triplet representation lets them adapt cyclic reduction and incremental Newton for component-wise stable square roots of M-matrices, with the stability claim holding up on the positivity arguments but worth checking in the singular case.","tokens_in":2329,"tokens_out":196,"would_cite":false,"duration_ms":41182,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"It is shown that these algorithms are component-wise numerically stable independently of the singularity of A and of its condition number."},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/BranchSelection.lean","rs_theorem":"branch_selection","paper_passage":"New versions of the Cyclic Reduction and the Incremental Newton iterations are provided in terms of triplets"}],"headline":"Numerical linear algebra for M-matrix square roots via triplet structure preservation","alignment":"orthogonal","rationale":"The paper's core contribution is the reformulation of Cyclic Reduction and Incremental Newton iterations to operate directly on triplet representations (P, u, v) of M-matrices, preserving nonnegativity and avoiding cancellation to obtain component-wise backward stability independent of cond(A) or singularity. This is a standard technique in structured numerical linear algebra exploiting the sign pattern and Perron-Frobenius properties of M-matrices (Theorems 1-4, Corollary 5, Algorithms 2-4). No RS-shaped elements appear: there is no recognition cost J(x) = ½(x + x⁻¹) − 1, no golden-ratio ladder, no 8-tick periodicity, no parameter-free derivation of physical constants, and no cosh-type functional equation. The work lies entirely in the domain of floating-point error analysis for structured matrices and does not engage the forcing chain or cost-function uniqueness theorems of the RS framework.","tokens_in":58931,"confidence":"high","tokens_out":372,"duration_ms":10418,"cache_read_input_tokens":32896,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"M-matrices admit triplet representations that let adapted iterations compute their principal square roots with component-wise stability independent of singularity or condition number.","keywords":["M-matrix","principal square root","component-wise stability","triplet representation","cyclic reduction","Newton iteration","numerical stability"],"falsifier":"Apply the triplet-based cyclic reduction or Newton iteration to a concrete singular M-matrix whose exact principal square root is known analytically, then check whether every component-wise relative error remains bounded by a small multiple of machine epsilon.","tokens_in":2582,"feed_emoji":"🧮","tokens_out":688,"duration_ms":37831,"temperature":0.7,"pith_summary":"The paper shows how to compute the principal square root of an M-matrix so that the error in each entry stays small relative to the entry itself. It represents the matrix A by a triplet (P, u, v) where P holds the negated off-diagonal entries, u is positive, and A u equals v. New versions of the cyclic reduction and incremental Newton methods are written to work directly with these triplets. If the original matrix has such a representation then its square root also has one, and the iterations preserve the structure while delivering component-wise accuracy that does not degrade when the matrix is singular or ill-conditioned. Numerical tests confirm the stability claims.","feed_headline":"Triplet structure yields stable square roots for M-matrices","feed_subtitle":"Adapted cyclic reduction and Newton iterations keep entrywise accuracy regardless of singularity or condition number.","key_machinery":"The triplet representation (P, u, v) of an M-matrix, which encodes off-diagonal structure in P and the relation A u = v, allowing structure-preserving reformulations of cyclic reduction and incremental Newton iterations.","core_discovery":"If an M-matrix A possesses a triplet representation (P, u, v) with u positive and v nonnegative, then its principal square root exists and likewise possesses a triplet representation. Reformulations of the cyclic reduction and incremental Newton iterations that operate on these triplets therefore compute the square root while remaining component-wise numerically stable, with the stability independent of whether A is singular and independent of the condition number of A.","pith_inferences":["The same triplet encoding might be adapted to compute other matrix functions such as the logarithm or exponential while retaining component-wise accuracy for M-matrices.","Applications that repeatedly form square roots of M-matrices arising from discretised differential operators could obtain more reliable results without extra conditioning safeguards.","Sparse implementations of the triplet iterations could be tested on large-scale problems from Markov chain analysis to measure practical speed and accuracy gains."],"forward_implications":["The computed square root is guaranteed to be an M-matrix that itself admits a triplet representation.","Component-wise relative errors are bounded independently of the condition number of the input matrix.","The same stability holds for both singular and nonsingular M-matrices.","The adapted iterations preserve the nonnegativity and structural properties required by the triplet form throughout the computation."],"fun_headline_variants":["Triplet reps stabilize M-matrix square roots","Stable sqrts for M-matrices via triplet iterations","Component-wise stable M-matrix sqrts with triplets","Triplet-based cyclic reduction for accurate M-matrix sqrts"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The input M-matrix admits a triplet (P, u, v) with u positive and v nonnegative, and the principal square root inherits a compatible triplet representation.","fun_headline_variants_meta":{"raw":{"variants":["Triplet reps stabilize M-matrix square roots","Stable sqrts for M-matrices via triplet iterations","Component-wise stable M-matrix sqrts with triplets","Triplet-based cyclic reduction for accurate M-matrix sqrts"]},"model":"grok-4.3","cost_usd":0.004695,"raw_usage":{"total_tokens":2221,"prompt_tokens":632,"num_sources_used":0,"completion_tokens":59,"cost_in_usd_ticks":46953000,"prompt_tokens_details":{"text_tokens":632,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1530,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":632,"tokens_out":59,"duration_ms":21785,"temperature":1.0,"reasoning_tokens":1530,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-22T09:01:21.774101+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Apply the triplet-based cyclic reduction or Newton iteration to a concrete singular M-matrix whose exact principal square root is known analytically, then check whether every component-wise relative error remains bounded by a small multiple of machine epsilon.","supporting_citations":[],"review_version":1}