{"id":"7a9c1aee-5b06-483b-a977-3acfe549aa02","arxiv_id":"2608.07724","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Two BSP algorithms for Bruhat decomposition achieve O(n^3/p) computation, O(n^2/p^(2/3)) communication, and a tunable synchronization cost, with the strip-recursive variant matching the best known trade-off for LU decomposition.","lead":"This paper designs two parallel algorithms for Bruhat decomposition, a matrix factorization used in numerical linear algebra. The algorithms are analyzed in the BSP model of parallel computation, which accounts for communication and synchronization costs as well as computation.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Correctness of the strip-recursive algorithm rests on Lemma 4 and an unproved recursion invariant; the one-line 'direct computation' proof does not show that later recursive elimination preserves previously reduced strips.","rationale":"The paper's headline contribution is the strip-recursive algorithm and its H-S trade-off. I checked the recurrences in Section 5.4; they solve to W=O(n^3/p), H=O(n^2/p^(2/3)) for alpha>=2/3, S=O(p^alpha), and the restriction alpha>=1/2 is consistent with W. So the cost analysis is not where the claim is vulnerable. The vulnerable point is correctness: the recursion in Section 5.3 is only as sound as Lemma 4 plus an invariant about previously reduced strips, and neither is proved. Lemma 4's proof is a one-line 'direct computation' and does not even state the recursive invariant explicitly. In a two-sided elimination with banded matrices, it is easy for left and right transformations to interfere; the boundary case where a pivot lies on the last antidiagonal of the reduced strip requires checking that L and U cancel on the pivot itself. I tested a small boundary example manually and the cancellation appears to work, so I am not claiming the lemma is false. But the paper gives no rigorous argument that the later recursive reduction of the second half-strip cannot reintroduce nonzeros in the rows/columns cleared by Lemma 4. Since the final claim that the algorithm produces a valid Bruhat decomposition depends entirely on this, the correctness risk is real. This matches the reader's weakest assumption; a completed proof or a randomized small-n test would settle it. The appropriate verdict remains CONDITIONAL: the approach is plausible and the costs are right, but the paper as written does not yet establish correctness.","tokens_in":10444,"tokens_out":41904,"duration_ms":374094,"concrete_test":"Run the strip-recursive algorithm of Section 5.3 on random nonsingular matrices of sizes n=8 and n=16 over Q (or GF(2)) with p=2 and p=4, using several strip widths n0 dividing n. After each recursive step, assert: (i) the previously reduced half-strip is unchanged and still consists of unit entries in its nonzeros; (ii) rows/columns containing a nonzero in that half-strip have no nonzero in the next strip; (iii) the final product LAU equals P. Any failed assertion is a concrete counterexample to the claimed correctness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strip-recursive algorithm's cost recurrences in Section 5.4 do solve to the claimed W=O(n^3/p), H=O(n^2/p^(2/3)) for alpha>=2/3, S=O(p^alpha), so the communication-synchronization trade-off is not the main risk. The load-bearing point is correctness. Section 5.2's Lemma 4 is the only mechanism for clearing the next antidiagonal strip before it is reduced, and its proof is a single 'Direct computation verifies' sentence. The lemma does not state the invariant needed by the recursion in Section 5.3: after step 3's recursive reduction of the second half-strip, the first half-strip must still be reduced, and the rows/columns that already contain a 1 in the first half-strip must still have no nonzeros in the second half-strip. Lemma 4 alone only describes one elimination step; it says nothing about the effect of the later recursive call, whose elimination matrices are also banded of bandwidth 2m. If those later matrices write into the rows/columns cleared by Lemma 4, the whole recursion collapses. No induction is given, so the central claim that the final LAU equals a permutation is unsupported. This is a proof gap at the exact place where the algorithm's correctness must be established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Bruhat decomposition in the BSP model, reformulated as the problem of computing matrices L, U and a subpermutation/permutation P such that LAU=P. It presents two recursive parallel algorithms. The block-recursive algorithm (Section 4) follows the standard LEU-decomposition recursion and derives recurrences for computation, communication, and synchronization costs, truncating the recursion at blocks of size n0=n/p^alpha to obtain a trade-off controlled by alpha. The strip-recursive algorithm (Section 5) partitions the matrix into antidiagonal strips, reduces strips recursively with banded elimination matrices, and claims costs W=O(n^3/p), H=O(n^2/p^(2/3)) for alpha>=2/3, and S=O(p^alpha), with alpha in [1/2,2/3]. The conclusion states that the strip-recursive trade-off matches the analogous trade-off of Tiskin for LU decomposition and generic pairwise elimination.","tokens_in":10652,"tokens_out":23241,"duration_ms":206256,"significance":"If the correctness of the strip-recursive construction can be established, the paper makes a substantial contribution: it provides a BSP algorithm for Bruhat decomposition with the optimal computation cost O(n^3/p), communication O(n^2/p^(2/3)), and a tunable synchronization cost O(p^alpha), matching the known trade-off for LU decomposition and generic pairwise elimination. The recurrences are explicit and parameter-free, and the comparison between the two recursion schemes is instructive. The main weakness is localized in the proof of the strip-recursive algorithm's correctness, where an essential induction invariant is asserted rather than proved.","major_comments":[{"comment":"The correctness of the strip-recursive algorithm is not established. Lemma 4 is the only mechanism that clears the rows and columns of the next half-strip before it is reduced, but its proof consists of the sentence 'Direct computation verifies' and does not show that the constructed L and U are simultaneously valid: applying L to eliminate columns can create new entries in rows that U is supposed to eliminate, and vice versa. More importantly, the recursive scheme in Section 5.3 applies Lemma 4 to the first half-strip, then makes a recursive call on the second half-strip, but no invariant is stated or proved to the effect that this second recursive call preserves (i) the already-reduced first half-strip and (ii) the zero rows and columns created by Lemma 4. Without such an induction, the final equality \\tilde L_m L'_m L_m A U_m U'_m \\tilde U_m = A_final does not imply that A_final is reduced, so the central claim that the algorithm produces a valid Bruhat decomposition is unsupported.","section":"Section 5.2, Lemma 4 and Section 5.3"},{"comment":"The summary line 'Overall we have obtained the following asymptotic costs: W(n,p)=O(n^3/p^(2/3))' is inconsistent with the recurrence-dag calculation immediately above it, which yields O(n^3/p), and with the subsequent truncation analysis, which requires alpha>=1/(3-log 3) precisely so that W_leaf=O(n^3/p). The displayed exponent 2/3 in the denominator is a load-bearing misstatement of the block-recursive algorithm's computation cost; the correct bound is W=O(n^3/p).","section":"Section 4.2, cost summary"},{"comment":"The proof of the banded matrix multiplication bound is not sufficiently specified to support the claimed costs. The text says blocks are formed by partitioning strips into 'regular parallelograms' and that 'the product of each pair of blocks requires O(m^2 n) operations', but it does not state the number of blocks, how processors are assigned, or why the per-processor computation is O(m^2 n/p). The claimed communication bound H=O(m^(4/3)n^(2/3)/p^(2/3)) is asserted without a derivation of the volume of data exchanged. Since Section 5.4's recurrences and the final H(n,p)=O(n^2/p^(2/3)) rely on Lemma 2, this gap is load-bearing for the strip-recursive cost analysis.","section":"Section 5.2, Lemma 2"}],"minor_comments":[{"comment":"The statement 'For every vertex u=(k0, lambda-j), ... w(u)=O(2^(3k0)), h(u)=O(2^(2k0))' contradicts the next displayed sums, which use 2^(3(k-k0)) and 2^(2(k-k0)); since log n0 = k-k0, the first pair should read O(2^(3(k-k0))) and O(2^(2(k-k0))).","section":"Section 4.2, leaf definitions"},{"comment":"The sentence 'vertices at this level have coordinates of the form (k-i, i-j)' does not match the stated interpretation of the horizontal coordinate as the logarithm of the number of processors; i-j is the number of diagonal steps, not the processor coordinate. Please define the coordinate transform explicitly.","section":"Section 4.2, recursion dag coordinates"},{"comment":"The quantities p_01 and p_10 are used in the formulas for l'' and u'' without being defined; they appear to be e_01 and e_10, and should be renamed or defined.","section":"Section 4.1, step 4"},{"comment":"The text says the banded matrix products are performed 'as described in steps 2 and 4', but Section 5.3 lists only three steps; the reference should be to steps 2 and 3.","section":"Section 5.4, first paragraph"},{"comment":"The range for the row index r in the construction of L appears to be off by one: for a row in the next strip, the condition should be stated consistently with the definition of the strip notation A<k+m, k+2m>, and the inclusive/exclusive endpoints should be checked. The current range k+m+1-j <= r <= k+2m+1-j does not match the strip A<k+m, k+2m> under the numbering introduced in the preceding paragraph.","section":"Section 5.2, Lemma 4 proof"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the unproved induction invariant for the strip-recursive algorithm; if the authors supply a complete proof of Lemma 4 and of the preservation invariant for the recursion, the paper could be acceptable. The cost computations are mostly sound apart from the Section 4.2 typo. The self-citations for BSP matrix multiplication and generic pairwise elimination are relevant and not, by themselves, a cause for concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the strip-recursive algorithm is a genuine new result: a BSP algorithm for Bruhat decomposition with W=O(n^3/p), H=O(n^2/p^{2/3}), S=O(p^alpha) for alpha in [1/2,2/3], matching Tiskin's trade-off for generic pairwise elimination. The cost recurrences are straightforward and, modulo minor typos, they solve correctly. Second, the paper is not yet rigorous. The correctness of the strip-recursive algorithm hangs entirely on Lemma 4, whose proof is one line of \"direct computation verifies\", and the recursion in Section 5.3 never states the invariant that later recursive eliminations preserve the already-reduced first half-strip. That is a real gap, not a stylistic quibble.\n\nWhat is new and good: the BSP cost analysis of Bruhat decomposition itself, and the antidiagonal strip recursion, are not in Malaschonok or Tiskin's earlier papers. Lemma 2 on banded matrix multiplication is a useful building block. The paper is honest about the relationship to prior work.\n\nSoft spots: the block-recursive section has genuine errors. The recursion-dag sum in Section 4.2 uses wrong exponents (e.g. 2j+3(k-i)+(i-j) should be 2j+3(k-i)-(i-j)), and the summary line lists W=O(n^3/p^{2/3}), which contradicts the paper's own later bound. These are fixable, but they are not cosmetic. More importantly, the \"special\" rows and columns in the block-recursive algorithm are mentioned and never defined. The strip-recursive part has a clean cost analysis, but the proof gap is load-bearing. Lemma 4 needs a real proof showing that the constructed L and U are banded as claimed and that the elimination does not disturb previously reduced strips. As written, there is no induction establishing that the final LAU equals a permutation.\n\nOverall: the central idea is plausible and the costs are likely correct, but the paper as submitted does not fully support its claims. It deserves a serious referee, but they should be asked to produce a complete proof of Lemma 4 and fix the block-recursive analysis.\n\nWho this is for: researchers in BSP algorithms and parallel numerical linear algebra. A reading group could usefully work through Lemma 4. I would not cite it in my own work until the correctness gap is closed.\n\nRecommendation: send to peer review, but expect major revision.","headline":"The strip-recursive BSP algorithm is a plausible new result with correct-looking costs, but the correctness proof rests on an unproved lemma and the block-recursive analysis has fixable typos.","tokens_in":11226,"tokens_out":5560,"would_cite":false,"duration_ms":47170,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W10","65F05","15A23"],"pacs":[],"model":"deepseek-v4-flash","headline":"A strip-recursive BSP algorithm computes the Bruhat decomposition of a non-singular $n\\times n$ matrix with computation cost $O(n^3/p)$, communication cost $O(n^2/p^{2/3})$ for $\\alpha\\geq 2/3$, and synchronization cost $O(p^\\alpha)$…","keywords":["bulk-synchronous parallel","Bruhat decomposition","LEU decomposition","banded matrices","communication cost","synchronization cost","block-recursive algorithm","strip-recursive algorithm"],"falsifier":"Construct a small matrix, say $n=4$ with a reduced strip $A\\langle 1,2\\rangle$ containing nonzeros in known rows and columns, build the matrices $L$ and $U$ exactly as Lemma 4 prescribes, multiply, and check whether every entry of the next strip lying in those rows and columns is zero and whether $L$ and $U$ remain within bandwidth $2m$; a single symbolic or numerical counterexample would refute the lemma and with it the algorithm's correctness.","tokens_in":10205,"feed_emoji":"🔀","tokens_out":16383,"duration_ms":124059,"temperature":0.7,"pith_summary":"The paper develops two parallel algorithms for Bruhat decomposition in the bulk-synchronous parallel (BSP) model of computation, where processors work locally and synchronize in supersteps. Bruhat decomposition expresses a non-singular square matrix as $A = U_1 P U_2$ with two upper-triangular matrices and a unique permutation matrix $P$, generalising LU decomposition while making pivoting structure explicit. The central result is that a strip-recursive algorithm, which reduces antidiagonal strips of width $n/p^\\alpha$ and eliminates with banded matrices, achieves computation cost $O(n^3/p)$, communication cost $O(n^2/p^{2/3})$ when $\\alpha\\geq 2/3$, and synchronization cost $O(p^\\alpha)$. For $\\alpha$ in $[1/2,2/3]$ this is a communication-synchronization trade-off that the paper states matches the analogous trade-off for LU decomposition and generic pairwise elimination. If correct, it shows Bruhat decomposition can be parallelised with the same communication profile as LU, without giving up the permutation structure that distinguishes it.","feed_headline":"Bruhat decomposition gets the same parallel costs as LU","feed_subtitle":"A strip-recursive BSP algorithm reaches the LU communication bound with a tunable superstep count.","key_machinery":"The machinery is the antidiagonal-strip recursion. The matrix is partitioned into strips of width $n_0 = n/p^\\alpha$; a strip is reduced when every row and column has at most one nonzero entry in the strip, equal to 1. Two lemmas carry the argument: multiplication of lower-banded matrices of bandwidth $m$ costs $W=O(m^2 n/p)$, $H=O(m^{4/3} n^{2/3}/p^{2/3})$, $S=O(1)$, and after reducing a strip, multiplication by lower- and upper-banded matrices of bandwidth $2m$ clears the marked rows and columns of the next strip. The recursion makes two half-strip calls per level, and the banded-matrix update between the calls is what keeps the communication cost below the cost of dense updates. The recursion depth $\\alpha\\log p$ is converted into the parameter $\\alpha$ that tunes the communication-synchronization trade-off.","core_discovery":"The central discovery is that the Bruhat decomposition $LAU = P$ can be computed in the BSP model by a recursion over antidiagonal strips that preserves the banded structure of the elimination. At each level, the first half of a strip is reduced recursively; then lower- and upper-banded matrices of bandwidth twice the strip width are used to clear the rows and columns of the adjacent strip that already contain nonzeros; then the second half is reduced recursively. The paper's cost analysis sums the recurrences to obtain $W=O(n^3/p)$, $H=O(n^2/p^{2/3})$ for $\\alpha\\geq 2/3$, and $S=O(p^\\alpha)$, with $\\alpha\\in[1/2,2/3]$ controlling the trade-off between communication and synchronization. In the range $\\alpha<2/3$ the communication cost is $O(n^2/p^\\alpha)$; at $\\alpha=2/3$ it saturates at $O(n^2/p^{2/3})$. The paper also analyzes a block-recursive algorithm with a similar structure, and presents the strip-recursive algorithm as the one with the better trade-off, matching the trade-off previously established for LU decomposition and generic pairwise elimination.","pith_inferences":["Beyond the paper, the same antidiagonal-strip elimination could apply to the generalized LEU decomposition of singular matrices, since the LEU base case is defined for all square matrices and not only for the non-singular case treated here.","Beyond the paper, the banded-matrix multiplication lemma is a reusable primitive: any banded linear-algebra routine that can be staged as products of banded matrices inherits the same communication costs.","Beyond the paper, an implementation could treat $\\alpha$ as a runtime parameter selected from hardware characteristics such as network bandwidth versus synchronization latency; the paper gives the asymptotic trade-off but not a rule for choosing $\\alpha$."],"forward_implications":["At the endpoint $\\alpha=2/3$, the strip-recursive algorithm attains $W=O(n^3/p)$, $H=O(n^2/p^{2/3})$, and $S=O(p^{2/3})$.","For every $\\alpha$ in $[1/2,2/3]$ the computation cost remains $O(n^3/p)$, so the trade-off changes only communication and synchronization, not arithmetic work.","Choosing a smaller $\\alpha$ reduces the number of supersteps but increases communication; choosing a larger $\\alpha$ reduces communication but increases supersteps, giving a one-parameter family of parallel algorithms for one problem.","When the permutation matrix is anti-diagonal, the Bruhat decomposition reduces to LU, so this algorithm specialises to an LU decomposition with the same communication and synchronization costs."],"supporting_citations":[{"why":"Supplies the BSP matrix multiplication routine and its costs used to update blocks throughout both recursive schemes.","marker":"[5]"},{"why":"Provides the LEU-decomposition existence result and sequential algorithm that forms the base case for reducing small blocks.","marker":"[4]"},{"why":"Introduces the connection between Bruhat decomposition and banded matrices that motivates the strip-recursive elimination structure.","marker":"[7]"},{"why":"Gives the communication-synchronization trade-off for LU decomposition and generic pairwise elimination that the strip-recursive algorithm claims to match.","marker":"[9]"},{"why":"Defines the BSP model, including the cost parameters $g$ and $l$ and the superstep structure that the paper's cost bounds are measured against.","marker":"[10]"}],"fun_headline_variants":["Bruhat decomposition matches LU communication costs","Parallel Bruhat hits LU's communication bound","Strip-recursive Bruhat matches LU efficiency","Bruhat decomposition now as efficient as LU","Communication-optimal Bruhat decomposition in BSP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the unproved assertion (Lemma 4) that after a strip is reduced, multiplication by the constructed banded matrices of bandwidth $2m$ clears the corresponding rows and columns of the next strip without disturbing already reduced strips; if that assertion fails, the recursive reduction does not produce a valid Bruhat decomposition.","fun_headline_variants_meta":{"raw":{"variants":["Bruhat decomposition matches LU communication costs","Parallel Bruhat hits LU's communication bound","Strip-recursive Bruhat matches LU efficiency","Bruhat decomposition now as efficient as LU","Communication-optimal Bruhat decomposition in BSP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000155,"raw_usage":{"total_tokens":1187,"prompt_tokens":890,"completion_tokens":297,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":229}},"tokens_in":506,"tokens_out":297,"duration_ms":2894,"temperature":1.0,"reasoning_tokens":229,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:21:42.685366+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small matrix, say $n=4$ with a reduced strip $A\\langle 1,2\\rangle$ containing nonzeros in known rows and columns, build the matrices $L$ and $U$ exactly as Lemma 4 prescribes, multiply, and check whether every entry of the next strip lying in those rows and columns is zero and whether $L$ and $U$ remain within bandwidth $2m$; a single symbolic or numerical counterexample would refute the lemma and with it the algorithm's correctness.","supporting_citations":[],"review_version":1}