{"id":"3ac801cb-8490-4aa3-8464-254355828558","arxiv_id":"2505.02977","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"ParAC parallelizes randomized approximate Cholesky factorization for Laplacian matrices using dynamic dependency tracking and no nested-dissection preprocessing, with CPU and GPU implementations that beat several standard preconditioners on many test problems.","lead":"This paper presents a parallel CPU and GPU algorithm for building approximate Cholesky preconditioners for large sparse Laplacian linear systems, using randomization to decide which fill-in entries to keep during elimination. It introduces dynamic dependency tracking so independent elimination steps run in parallel without costly nested-dissection preprocessing, and benchmarks it against Hypre, AmgX, and incomplete Cholesky on a range of matrices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Dependency-count scheduling is unproven; an instrumentation assertion on column readiness would settle whether the parallel schedule preserves the sequential AC factor.","rationale":"The reader's weakest assumption identifies the same load-bearing point: the correctness of dynamic dependency tracking is asserted without proof, and if it fails, the parallel factor no longer matches the sequential randomized Cholesky factor whose statistical guarantees (E(GG^T)=L) underpin the method. I agree with this concern and with the CONDITIONAL verdict. I do not see a concrete counterexample in the manuscript, and the invariant is plausible enough that the right next step is an empirical instrumentation test rather than rejection. The concrete test is targeted and cheap: it directly checks the sufficient condition at the moment of elimination, and it can be run on both exhaustive small graphs and the paper's own benchmark suite. If the test passes, the concern reduces to a missing proof, which a revised version can supply by induction on the elimination steps; if it fails, the central claim collapses. Either way, the reader's conditional acceptance is the appropriate posture, so no verdict change is needed.","tokens_in":18893,"tokens_out":15356,"duration_ms":191750,"concrete_test":"Instrument the ParAC CPU implementation to assert, immediately before vertex k is eliminated and after assembling its neighbor list N_k, that the Schur-complement column of k contains no off-diagonal nonzero with row index < k (equivalently, that dp[k]==0 implies no pending updates from any lower-labeled eliminated vertex). Run this assertion on (a) all unweighted graphs up to n=8 vertices under every vertex ordering and a fixed RNG seed, and (b) the Table 1 benchmark matrices with AMD, nnz-sort, and random orderings. If the assertion ever fails, the dependency count is not sufficient and the parallel factor can diverge from sequential AC; if it never fails across the corpus, the schedule invariant is empirically confirmed and the remaining gap is only the missing formal proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central correctness claim is that the dynamic dependency count dp[i] — initialized to the number of lower-labeled neighbors and updated by +1 for each new edge and −multiplicity for each cut edge — exactly determines when vertex i is safe to eliminate. If dp[i]=0 while some Schur-complement update from an already-eliminated lower-labeled vertex is still pending, then the parallel elimination order departs from the intended fixed ordering and the resulting (G,D) no longer follows the randomized AC distribution, invalidating E(GG^T)=L and all preconditioner-quality arguments derived from the sequential algorithm. The paper gives no proof of this invariant in Section 4.2; it only asserts that 'the impact of direct one-hop neighbors is still guaranteed' and that counting lower-labeled neighbors suffices. This is load-bearing because the entire contribution — dynamic parallelism without nested dissection — rests on the schedule being exactly the AC elimination order, not merely a plausible ordering. The concern is concrete: the scheduling does not enforce the full label order (independent higher-labeled vertices can be eliminated before lower-labeled ones), so correctness depends entirely on the count being a sufficient condition, and no argument, lemma, or experiment in the manuscript verifies that condition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ParAC, a parallel algorithm for constructing randomized approximate Cholesky (AC) preconditioners for large sparse Laplacian systems. The key idea is to replace the usual nested-dissection preprocessing with a dynamic dependency-counting scheduler: each vertex maintains a count of lower-labeled dependencies, initialized from the original graph and updated as edges are cut or sampled fill-in edges are added; vertices whose count reaches zero are scheduled for elimination. The paper presents CPU and GPU implementations, with the GPU version using a persistent kernel, a hash-map workspace, and block-level sorting/sampling. Experiments on matrices up to 50M vertices compare ParAC against Hypre, AmgX, MATLAB ichol, and cuSPARSE ichol(0), reporting that ParAC is competitive with and often faster than the incomplete-Cholesky baselines on irregular graph problems.","tokens_in":19162,"tokens_out":21410,"duration_ms":264435,"significance":"If the correctness of the dynamic scheduling is established, this is a valuable practical contribution: it demonstrates that randomized incomplete Cholesky can be parallelized on GPUs without expensive symbolic preprocessing, and it provides an open-source implementation. The dynamic dependency-counting idea is clean and potentially applicable to other randomized factorization schemes. The empirical study is broad and uses realistic large-scale matrices. However, the central correctness claim--that the parallel schedule reproduces the sequential AC elimination--is only argued informally, which tempers the significance until that gap is closed.","major_comments":[{"comment":"The sufficiency of the dynamic dependency count is asserted but not proved. The paper should state and prove an invariant: for every remaining vertex v, dp[v] equals the total multiplicity of edges between v and lower-labeled remaining vertices in the current elimination graph. From this invariant one must show by induction that any vertex with dp=0 can be eliminated safely, i.e., its Schur-complement column is identical to the one in the sequential AC factorization, and that eliminating higher-labeled vertices early cannot affect lower-labeled vertices. In particular, the manuscript should justify that a ready vertex has no lower-labeled neighbors, so that the cut-edge update in line 23 only decrements dp for higher-labeled vertices. This is load-bearing because the entire contribution--parallelism without nested dissection--rests on the schedule reproducing the AC elimination order and distribution.","section":"Section 4.2, Algorithms 3 and 4"},{"comment":"The expectation property E(GG^T)=L is cited for the sequential AC algorithm, but the paper does not show that ParAC's output has the same distribution. Without such a proof, the preconditioner-quality claims derived from the sequential algorithm do not automatically transfer to ParAC. The experiments do not check distributional equivalence either. I request either a formal proof that the parallel schedule preserves the sequential distribution, or an explicit experiment comparing ParAC's factor against the sequential AC factor on the same graph and random seed to validate that the sampled fill-in distribution is unchanged.","section":"Section 2.2 vs. Section 4"},{"comment":"The total memory for the triangular factor is estimated 'with the help of empirical observation.' For a reproducible and robust solver, the paper should specify how the allocation size is chosen and what happens if the estimate is exceeded. Since the GPU implementation allocates device memory up front and the randomized fill-in count is not a priori bounded, a bad estimate would cause kernel failure or silent truncation. This is a practical correctness concern for the delivered software, even though it does not affect the algorithmic idea itself.","section":"Section 5.2.1"}],"minor_comments":[{"comment":"The update 'dp[i] -= N(i).multiplicity' should be annotated to explain that all neighbors i of a ready vertex k have label greater than k; otherwise the pseudocode appears to decrement dp for lower-labeled neighbors, which would be incorrect. This point is implicit in the text but should be explicit.","section":"Algorithms 3 and 4, line 23"},{"comment":"ParAC is a randomized algorithm, but the reported runtimes and fill-in counts appear to be from single runs. The paper should report means and standard deviations over several trials, especially for the performance comparisons where the claimed advantage is on the order of 1.5-2x.","section":"Section 6, Table 3"},{"comment":"The 'nnz-sort' ordering is used in several figures and tables but is only described informally in the text. Please define it precisely, including the tie-breaking rule used for vertices with equal initial degree.","section":"Section 6"},{"comment":"The expression for D(k,k) is garbled in the pseudocode; it should read D(k,k) = sum_{i in N_k} |l_{ki}|, consistent with the Laplacian diagonal.","section":"Algorithms 3 and 4, line 14"},{"comment":"There are several typos and stylistic issues: 'crtical' in Figure 4, inconsistent 'HyPre'/'Hypre' in Section 6, and 'phenomenal results' in Section 6.2 is subjective and should be replaced with a quantitative statement.","section":"Various"}],"recommendation":"major_revision","confidential_remarks":"The core scheduling idea appears sound and the experimental evidence is strong, but the missing correctness proof for the dependency-count invariant is a genuine gap in a paper whose central claim is about parallelizing a randomized factorization. I would encourage the editor to request a rigorous lemma or at least a formal invariant statement; the informal argument in Section 4.2 is plausible but not sufficient for the claims made. Adding a small experiment comparing ParAC's factor to the sequential AC factor would also materially increase confidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper: it is a genuine systems contribution, and its core scheduling correctness is argued informally rather than proven. If you work on parallel sparse solvers, it is worth your time.\n\nThe new idea is dynamic dependency counting for randomized approximate Cholesky. Instead of computing a nested dissection to find independent domains, ParAC fixes an elimination ordering and tracks, per vertex, how many lower-labeled neighbors currently have edges into it. When that count hits zero, the vertex is ready. This is a clean way to expose parallelism from the sampled fill-in structure, and the paper explains why the classic elimination tree is overly restrictive. The GPU persistent-kernel design, including the block-level sorting and hash-map insertion, is also solid engineering.\n\nWhat the paper does well: the experiments span a wide range of matrices, from PDEs to road networks and social graphs, and they compare against Hypre, AmgX, MATLAB ichol, and cuSPARSE ichol(0). On GPU, ParAC beats cuSPARSE in both factorization time and iteration count on most problems, and it beats AmgX on several irregular graphs. The CPU results also show clear superiority over MATLAB ichol. The writing is clear, and the intuition about sampling cutting dependencies is well presented.\n\nSoft spots, in proportion: the dependency-count scheduling is load-bearing, and Section 4.2 gives only an informal argument that the counts are sufficient. I do not think this is fatal—the counting is essentially the standard elimination-graph bookkeeping, and the experimental results back it up—but a short invariant proof or an assertion that the parallel schedule produces the same factor as the sequential AC algorithm would remove lingering doubt. Missing too is a direct comparison against Rchol, the prior parallel randomized Cholesky that uses nested dissection. Without that, the claim of eliminating preprocessing is not fully demonstrated. Also, for a randomized method, there are no error bars or repeated trials, which would be a nice addition but is not disqualifying.\n\nThis paper is for HPC researchers working on incomplete factorizations and anyone using Laplacian solvers on large graphs. It deserves a serious referee and likely acceptance after revision.\n\nMy recommendation: send it to peer review. Ask the authors to add a short correctness argument for the dependency invariant and a head-to-head with Rchol. The rest is solid.","headline":"ParAC's dynamic dependency tracking is a plausible and useful way to parallelize randomized Cholesky without nested dissection, and the GPU implementation makes it competitive in practice; the main gaps are the missing formal correctness argument and a missing direct comparison with Rchol.","tokens_in":19644,"tokens_out":6989,"would_cite":true,"duration_ms":85491,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F08","65F50","68W20","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"ParAC dynamically discovers parallelism during randomized Cholesky factorization, eliminating nested-dissection preprocessing while matching or outperforming specialized solvers on CPU and GPU.","keywords":["randomized Cholesky","graph Laplacian","preconditioner","parallel factorization","GPU computing","dynamic dependency tracking","incomplete factorization","sparse linear systems"],"falsifier":"Instrument ParAC to record, for each eliminated vertex, the identity of each lower-numbered neighbor whose Schur-complement update contributed to its column, and verify that the vertex's dependency count reached zero only after all such updates were applied; then compare the resulting factor with the sequential AC factor on the same ordering and test $\\mathbb{E}(GG^\\top)=L$ by Monte Carlo. If any schedule eliminates a vertex before a required update reaches it, the central claim fails.","tokens_in":18740,"feed_emoji":"⚡","tokens_out":9601,"duration_ms":98231,"temperature":0.7,"pith_summary":"This paper introduces ParAC, a parallel algorithm for building approximate Cholesky preconditioners for graph-Laplacian linear systems. The method keeps the randomized fill-in sampling of the AC algorithm but replaces the usual symbolic preprocessing, such as nested dissection, with a dynamic dependency counter that reveals which vertices can be eliminated in parallel as factorization proceeds. The paper reports CPU and GPU implementations and benchmarks them against algebraic-multigrid and incomplete-Cholesky solvers, with ParAC generally competitive or faster on irregular graph problems and much faster to construct in many cases. If the approach holds, randomized preconditioners for Laplacians become practical on many-core hardware without the heavy setup cost that previously limited them.","feed_headline":"GPU randomized Cholesky skips the costly preprocessing","feed_subtitle":"Dynamic dependency tracking turns random fill-ins into parallel work, rivaling established solvers.","key_machinery":"The load-bearing object is the dynamic dependency count on the elimination graph viewed as a multigraph. Initially each vertex $i$ has a count equal to the number of neighbors $j<i$; when an edge is cut, the count of the larger-index vertex decreases by the edge multiplicity, and when a new sampled edge $(a,b)$ is formed, the count of $\\max(a,b)$ increases by one. A vertex becomes eligible exactly when this count hits zero. This counter, together with the randomized spanning-tree sampling step of the AC algorithm, is what converts an unknown sparsity pattern into a schedule of independent eliminations.","core_discovery":"The central claim is that, although randomized fill-ins make the sparsity pattern of the factorization unknown in advance, parallelism can still be found on the fly: each vertex keeps a count of the lower-numbered neighbors it must wait for, the count is incremented when a newly sampled edge points to it and decremented when an edge involving it is cut, and any vertex whose count reaches zero is immediately ready to eliminate. Because the randomized sampler only forms a spanning tree among the neighbors instead of a full clique, many serial dependencies of the classical elimination tree are severed, so the dynamic counts expose far more parallelism than the classical e-tree would predict. The paper argues that this removes the need for nested-dissection-based scheduling, and the experiments show that the resulting preconditioner is competitive with established solvers on CPUs and GPUs, with the GPU version faster than sparse incomplete-Cholesky on many tested problems.","pith_inferences":["Editorial inference: if a rigorous proof of the dependency-count rule can be supplied, the same dynamic-scheduling idea may extend to other randomized incomplete factorizations, including nonsymmetric ones, wherever fill-in positions are random.","Editorial inference: the paper's analogy to parallel maximal independent set suggests a testable bound: for random vertex orderings, the number of parallel elimination rounds may be polylogarithmic with high probability; measuring round count versus $N$ on random graphs would check this.","Editorial inference: because critical-path length, not fill count, governs GPU time, one could search for elimination orderings that directly minimize the depth of the sampled spanning-tree structure, for instance by labeling vertices to keep the dynamic dependency DAG shallow."],"forward_implications":["Randomized approximate Cholesky preconditioners can be constructed in parallel without nested dissection, cutting preprocessing time so that one-off solves and repeatedly changing inputs become practical.","On GPUs, a persistent-kernel, right-looking variant with one warp per vertex makes the construction bandwidth-bound and competitive with specialized algebraic-multigrid solvers on irregular graph Laplacians.","Elimination ordering has little effect on the number of nonzeros in the factor but strongly affects the critical path, so cheap orderings like nnz-sort or random permutation are preferable on GPUs.","Because the factor satisfies $\\mathbb{E}(GG^\\top)=L$ and is stable across runs, the preconditioner can be used as a drop-in algebraic preconditioner for symmetric diagonally dominant systems, and in combination with sketching it supports fast graph sparsification."],"supporting_citations":[{"why":"defines the randomized approximate Gaussian elimination (AC) algorithm that ParAC parallelizes.","marker":"[37]"},{"why":"provides the practical AC variant with the sampling scheme and the expectation property $\\mathbb{E}(GG^\\top)=L$.","marker":"[23]"},{"why":"is the prior parallel randomized-Cholesky implementation that ParAC improves on by removing the nested-dissection preprocessing step.","marker":"[10]"},{"why":"supplies the elimination-graph dependency lemma (restated as Lemma 4.1) on which the dynamic dependency reasoning rests.","marker":"[48]"},{"why":"is the parallel block-sampling Laplacian solver whose theoretical construction contrasts with ParAC's dynamic scheduling.","marker":"[50]"},{"why":"is the parallel approximate-Gaussian-elimination framework whose independent-set ideas overlap with ParAC's dynamic scheduling.","marker":"[6]"},{"why":"is the algebraic-multigrid baseline used in the CPU performance comparison.","marker":"[31]"},{"why":"is the GPU algebraic-multigrid library used as a baseline in the GPU experiments.","marker":"[46]"}],"fun_headline_variants":["GPU randomized Cholesky: on-the-fly parallelism, no pre-scheduling","Randomized Cholesky: dynamic counts reveal GPU parallelism instantly","No pre-sorting: randomized Cholesky tracks dependencies on GPU","Random fill-ins? Dynamic counting makes them parallel on GPUs","GPU preconditioner: randomized Cholesky skips the preordering step"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument collapses if a vertex's dependency count can reach zero before every Schur-complement update from lower-numbered vertices has been applied to it; the paper states the update rule but gives no formal proof that the count is a complete criterion.","fun_headline_variants_meta":{"raw":{"variants":["GPU randomized Cholesky: on-the-fly parallelism, no pre-scheduling","Randomized Cholesky: dynamic counts reveal GPU parallelism instantly","No pre-sorting: randomized Cholesky tracks dependencies on GPU","Random fill-ins? Dynamic counting makes them parallel on GPUs","GPU preconditioner: randomized Cholesky skips the preordering step"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000768,"raw_usage":{"total_tokens":3383,"prompt_tokens":905,"completion_tokens":2478,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":2385}},"tokens_in":521,"tokens_out":2478,"duration_ms":18989,"temperature":1.0,"reasoning_tokens":2385,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:37:58.232262+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument ParAC to record, for each eliminated vertex, the identity of each lower-numbered neighbor whose Schur-complement update contributed to its column, and verify that the vertex's dependency count reached zero only after all such updates were applied; then compare the resulting factor with the sequential AC factor on the same ordering and test $\\mathbb{E}(GG^\\top)=L$ by Monte Carlo. If any schedule eliminates a vertex before a required update reaches it, the central claim fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines the randomized approximate Gaussian elimination (AC) algorithm that ParAC parallelizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the elimination-graph dependency lemma (restated as Lemma 4.1) on which the dynamic dependency reasoning rests."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"is the parallel block-sampling Laplacian solver whose theoretical construction contrasts with ParAC's dynamic scheduling."},{"cited_title":"d.].hypre: High Performance Preconditioners","cited_arxiv_id":null,"evidence_quote":"is the algebraic-multigrid baseline used in the CPU performance comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"is the GPU algebraic-multigrid library used as a baseline in the GPU experiments."}],"review_version":1}