{"id":"b56b890a-6870-444b-96f0-c6b6d3ec72a9","arxiv_id":"2602.00898","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A patch-based nested-dissection permutation that builds the elimination tree as it reorders cuts sparse Cholesky preprocessing time by up to ~10x and end-to-end solve time by up to ~6.6x on mesh problems.","lead":"This paper presents a faster way to reorder the equations in large sparse linear systems that come from triangle meshes, so direct solvers can factor them more quickly. The speedup comes from replacing expensive balanced graph partitioning with a coarser mesh-patch ordering and reusing it, which matters for graphics workloads that repeatedly solve such systems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"cuDSS integration supplies an etree without verifying it matches the true elimination tree; an incorrect etree could invalidate the end-to-end speedup claim.","rationale":"The reader's weakest assumption concerns matrix-mesh correspondence affecting performance transferability; my concern is about etree correctness in the cuDSS integration, which threatens the validity of the reported end-to-end speedups even within the paper's stated scope. Both are load-bearing, but they are distinct: one is about performance generality, the other about correctness of the experimental integration. The paper's evaluation is otherwise credible—it isolates the permutation stage, reports break-even iterations, and leaves numerical factorization untouched—so the appropriate verdict remains CONDITIONAL, with the etree validation as an additional required revision. The concern is not a demonstrated flaw, but a missing verification that is necessary to trust the central claim.","tokens_in":20211,"tokens_out":17616,"duration_ms":196737,"concrete_test":"For each benchmark in Table 1, compute the etree produced by the algorithm for the same permutation, compute the true etree from the permuted matrix using a standard routine (e.g., CHOLMOD's symbfact), and compare parent relationships at every node. Then run the cuDSS solve with the supplied etree and measure the relative residual ||b - A x|| / ||b|| against a reference solver (e.g., Intel MKL or CHOLMOD). If any etree parent mismatches or any residual exceeds 1e-8, the integration is invalid and the end-to-end speedup numbers do not reflect correct solves.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline speedups are measured by replacing cuDSS's permutation and elimination-tree construction with the algorithm's outputs. Correct integration requires that the supplied etree be the exact elimination tree of the permuted matrix; otherwise the wavefront schedule cuDSS uses can violate data dependencies, producing incorrect factorization results or runtime failure (§5 explicitly warns that an incompatible schedule can lead to runtime failure). The algorithm builds the etree by making each separator and each leaf subgraph a single node, but leaf subgraphs are locally reordered with AMD (§4.3). The internal elimination dependencies within a leaf are not represented in the etree; if cuDSS treats a leaf as a single supernode and schedules its internal elimination without respecting those dependencies, the factorization can be wrong. The paper never reports numerical residuals, comparison with a reference direct solver, or any verification that the separators chosen at the quotient level are valid vertex separators of the current subgraph. Since the central claim is an end-to-end speedup presupposing correct solves, the absence of etree validation is a load-bearing gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a patch-based nested-dissection permutation for sparse SPD systems whose sparsity graph is the adjacency graph of a triangle mesh. It computes a patch partition, lifts it to a group map, recursively bipartitions the quotient graph to obtain separators, builds a coarse elimination tree, and assembles the final permutation by concatenating local orderings (AMD) in a chosen schedule. The authors integrate the method into NVIDIA cuDSS and Intel MKL, replacing the default ordering and, for cuDSS, the elimination-tree construction. They report ordering-time speedups up to 10.27× vs METIS and end-to-end solve speedups up to 6.62×, with ablations showing the effect of patch size, separator computation, and local ordering.","tokens_in":20388,"tokens_out":12833,"duration_ms":145921,"significance":"If the claims are correct, this is a practically useful result for graphics workloads where the symbolic phase dominates sparse Cholesky. The paper is unusually transparent: it leaves the numerical factorization untouched when measuring integration effects, isolates the contributions of patch size, separator computation, and local ordering, reports break-even iteration counts, and releases code. The main gap is that the correctness of the cuDSS integration—specifically, the validity of the user-supplied elimination tree—is never verified, which is a prerequisite for any end-to-end timing claim.","major_comments":[{"comment":"The central end-to-end speedup claims for cuDSS presuppose that the elimination tree handed to cuDSS is a valid schedule for the permuted matrix. The etree is built by making each separator and each leaf subgraph a single node, while leaves are locally reordered with AMD (§4.3). The internal elimination dependencies inside a leaf are therefore not represented in the etree. §5 warns that an incompatible schedule can cause runtime failure, but the evaluation reports no numerical residuals, no comparison against a reference direct solve, and no check that the separators used at each level are valid vertex separators of the current subgraph. Without such validation, the timings in Table 1 and Fig. 7 could reflect incorrect solves rather than genuine speedups. Please add residual/normwise-error checks for all benchmark configurations and verify (or construct) the exact etree of the final perm","section":"§5, §4.2–4.3, §6"}],"minor_comments":[{"comment":"The abstract reports 'up to 6.27×' end-to-end speedup, while §1 and Fig. 1 report 'up to 6.62×'. Please reconcile.","section":"§1, abstract"},{"comment":"AMD is cited as [Tobler and Maierhofer 2006], which is a mesh data structure paper; the correct reference for AMD is Amestoy et al. 1996. Similarly, §3 cites [Ashkiani et al. 2018] for NP-completeness of fill-in minimization; the correct citation is Yannakakis 1981.","section":"§2, references"},{"comment":"The sentence 'Hence, speedups here are smaller than for mesh smoothing (§6.4), permutation accounts for a larger share of runtime' contradicts the immediately preceding observation that increased density reduces the fraction of time spent in permutation. Presumably 'larger' should be 'smaller.'","section":"§6.5"},{"comment":"Algorithm 1 lists target_patch_size as a parameter only implicitly; the input line says 'A, M, nd_level' but GetPatches uses a patch-size parameter. Please include all tunable parameters explicitly and report the nd_level sensitivity. The paper sets nd_level to 9–10 with a citation but provides no ablation for it.","section":"Algorithm 1 / §4"},{"comment":"The text says the quotient graph is built once and then updated, but Algorithm 2 calls QuotientGraph(g, gmap) at every recursion level. Please clarify whether the initial construction is reused and only node/edge weights are updated.","section":"§5"},{"comment":"The title and abstract emphasize 'Sparse Matrix Permutation' broadly; the method actually requires the matrix sparsity graph to coincide with a triangle-mesh adjacency graph (or a block-wise contraction of it). A short formal statement of this precondition would make the contribution easier to evaluate and avoid overgeneralization.","section":"§2 / title"}],"recommendation":"major_revision","confidential_remarks":"The paper is close: the empirical methodology is strong, the ablation is honest, and the code is available. The single load-bearing issue is the unvalidated cuDSS etree integration. This is fixable with a revision that adds numerical correctness checks and, if necessary, constructs a true etree from the final permutation. I would be supportive of acceptance once that is addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the core idea is genuinely new and the empirical work is transparent enough to be useful: patch-level nested dissection on a single reused quotient graph, with the elimination tree built as a byproduct and a schedule that can be swapped for CPU or GPU solvers. When each patch is a single vertex, it reduces to classical nested dissection. The authors integrate into cuDSS and MKL, leave the numerical factorization untouched, isolate the permutation effect, and even give break-even iteration counts in Table 1. That is the right way to report an ordering-quality versus runtime trade-off. Second, there is one gap that needs fixing before I'd trust the end-to-end speedups: they hand cuDSS an elimination tree whose leaves are single nodes containing thousands of vertices that were locally reordered with AMD. That collapsed tree is not the true elimination tree of the permuted matrix, and the paper never verifies that the solves are actually correct—no residuals, no comparison against a reference solver, no check that the separators are valid vertex separators. If cuDSS schedules internal elimination of those leaf blocks without respecting the AMD order, the factorization can be wrong. The applications would likely look terrible in that case, so the reported speedups are probably on real solutions, but \"probably\" isn't good enough for a paper whose central claim is an end-to-end speedup.\n\nThe smaller issues are easy to fix but real: the abstract says 6.27x, the caption and intro say 6.62x; the citation for AMD points to Tobler & Maierhofer (a mesh data structure paper) instead of Amestoy et al., and the NP-completeness citation is to Ashkiani et al. (a dynamic hash table paper); the normal-equation derivation in §6.2 is off by a factor—it should be (M + α L^T M^{-1} L)x = M y, not the printed form. Also, no run-to-run variance and no full input list. None of these breaks the core claim.\n\nWhat holds up: the central claim is credible. The ablations isolate the contribution of each design choice, the baseline comparisons are against real tools, and the break-even analysis is a nice touch. The method is clearly scoped to triangle-mesh SPD systems, and the authors say so.\n\nWho this is for: anyone working on sparse direct solvers for mesh-derived systems, especially on GPUs with cuDSS. Send it to peer review; require a correctness check on the etree and fix the mechanical issues before acceptance.","headline":"Solid and genuinely new systems work with transparent ablations, but the unverified elimination tree handed to cuDSS is a real gap that needs fixing before the end-to-end claims can be trusted.","tokens_in":20949,"tokens_out":7353,"would_cite":true,"duration_ms":78355,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F05","65F50"],"pacs":[],"model":"deepseek-v4-flash","headline":"A mesh-aware, patch-guided nested-dissection permutation cuts fill-reducing ordering time by up to 10.27x and end-to-end sparse-Cholesky solve time by up to 6.62x on large triangle-mesh systems without unacceptable fill-in.","keywords":["fill-reducing permutation","nested dissection","sparse Cholesky","elimination tree","triangle meshes","quotient graph","direct solvers","GPU solvers"],"falsifier":"On a 1.5M-vertex triangle-mesh Laplacian, measure ordering time and the Cholesky fill ratio for the patch-guided permutation against a balanced nested-dissection permutation on the same hardware; the claim fails if the ordering-time advantage disappears or the fill ratio grows by more than the paper's own reported bounds (roughly +15%) at large patch counts.","tokens_in":20069,"feed_emoji":"⚡","tokens_out":4221,"duration_ms":43589,"temperature":0.7,"pith_summary":"The paper sets out to show that for linear systems coming from triangle meshes, the most expensive part of a sparse direct solver—the fill-reducing permutation—can be made dramatically faster by deliberately relaxing the two design goals that general-purpose nested-dissection tools chase: strict balance and minimal separator size. Instead of coarsening the whole graph level by level, the algorithm clusters mesh vertices into patches, builds one compact quotient graph, and runs nested dissection on that small graph at every recursion. It also constructs the elimination tree on the way, so the solver's symbolic phase can reuse that hierarchy. A sympathetic reader would see the claim as: for mesh-shaped matrices, preprocessing time can drop by an order of magnitude while the resulting factorization remains efficient enough to yield end-to-end speedups on big problems.","feed_headline":"Mesh-patch ordering cuts permutation time 10x, speeds solves 6.6x","feed_subtitle":"By relaxing strict separator balance and reusing a compact quotient graph, a mesh-native permutation keeps direct Cholesky fast on large pro","key_machinery":"The central object is the quotient graph of a mesh-patch partition: nodes are connected patches of mesh vertices, edges record adjacency across patches, and each patch is lifted to a group of vertices in the matrix graph. Separator search is done on this quotient graph at every recursion level; a bipartition of the quotient graph is lifted to a separator superset of actual graph vertices and then locally refined. Because the same patch structure is reused across all recursive calls, the algorithm avoids repeated multilevel coarsening. The elimination tree is built as the recursion produces separators, and the final permutation is a concatenation of local orderings (some minimum-degree style)","core_discovery":"On the paper's own terms, the discovery is that a nested-dissection permutation for a mesh-derived matrix can be computed by first partitioning the mesh into connected patches, lifting that partition to the matrix graph as a group map, recursing only on the resulting quotient graph, and then refining the lifted separator sets with a local ordering step such as approximate minimum degree. This patch-guided recursion produces a near-nested-dissection ordering and its accompanying elimination tree in one pass. Because the quotient graph is much smaller than the input graph and is reused at every recursion level, separator computation and tree construction become cheap; the price is a modest inc","pith_inferences":["The same patch-guided separator mechanism could plausibly transfer to other mesh types (tetrahedral, hexahedral) if fast volumetric patching becomes available; the paper's preliminary tet experiment hints at this direction.","Because the schedule is a free parameter that does not affect fill-in, the approach opens an easy path to solver-specific scheduling optimization without recomputing the ordering.","The fill-in–runtime trade-off could be tuned per application by adjusting patch size; large patches favor speed, small patches favor factor quality, suggesting an auto-tuning knob for different solver pipelines."],"forward_implications":["On meshes above roughly 50k–100k vertices, the patch-guided ordering beats general-purpose ordering tools in runtime, with up to a 10.27x ordering speedup and a 4.58x geometric mean.","End-to-end sparse-Cholesky solves on large meshes speed up by up to 6.62x on a GPU solver and 2.55x on a CPU solver, with the gains growing as permutation dominates preprocessing.","The elimination tree is produced together with the permutation, so symbolic analysis can reuse it, removing a separate tree-construction step.","The schedule used to concatenate local orderings can be chosen without changing fill-in, allowing the same permutation to adapt to different execution models—post-order for CPU locality, level-order/wavefront for GPU parallelism.","For repeated-factorization workloads, the speedup persists beyond a break-even iteration count (reported 148–160 iterations for mesh smoothing)."],"fun_headline_variants":["Mesh-native permutation speeds sparse solves 6.3x","Relaxed separator ordering cuts Cholesky time 6.3x","Patch-based ordering boosts direct solvers 6.3x","Quotient-graph permutation accelerates mesh solves","Fast mesh permutation: up to 6.27x faster Cholesky"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The speedups depend on the matrix's sparsity graph matching the triangle-mesh adjacency graph, so that patches of mesh vertices correspond to groups of matrix rows/columns; for matrices without that correspondence (e.g., higher-order elements or constrained degrees of freedom), the patch-guided separator search loses its foundation.","fun_headline_variants_meta":{"raw":{"variants":["Mesh-native permutation speeds sparse solves 6.3x","Relaxed separator ordering cuts Cholesky time 6.3x","Patch-based ordering boosts direct solvers 6.3x","Quotient-graph permutation accelerates mesh solves","Fast mesh permutation: up to 6.27x faster Cholesky"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000663,"raw_usage":{"total_tokens":2834,"prompt_tokens":679,"completion_tokens":2155,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":423,"completion_tokens_details":{"reasoning_tokens":2067}},"tokens_in":423,"tokens_out":2155,"duration_ms":17381,"temperature":1.0,"reasoning_tokens":2067,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T05:51:47.861689+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a 1.5M-vertex triangle-mesh Laplacian, measure ordering time and the Cholesky fill ratio for the patch-guided permutation against a balanced nested-dissection permutation on the same hardware; the claim fails if the ordering-time advantage disappears or the fill ratio grows by more than the paper's own reported bounds (roughly +15%) at large patch counts.","supporting_citations":[],"review_version":1}