Pith. sign in

REVIEW 3 major objections 5 minor 56 references

Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read ParAC dynamically discovers parallelism during randomized Cholesky factorization, eliminating nested-dissection preprocessing while matching or outperforming specialized solvers on CPU and GPU.

desk verdict 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. read the letter →

arxiv 2505.02977 v2 pith:5TOGHKPA submitted 2025-05-05 cs.DC cs.DScs.NAmath.NA

Tianyu Liang , Chao Chen , Yotam Yaniv , Hengrui Luo , David Tench , Xiaoye S. Li , Aydin Buluc , James Demmel This is my paper · ORCID
classification cs.DCcs.DScs.NAmath.NA MSC 65F0865F5068W2005C50
keywords randomizedCholeskygraphLaplacianpreconditionerparallelfactorizationGPUcomputingdynamicdependencytrackingincompletesparselinearsystems
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 4.2, Algorithms 3 and 4] 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.
  2. [Section 2.2 vs. Section 4] 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.
  3. [Section 5.2.1] 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.
minor comments (5)
  1. [Algorithms 3 and 4, line 23] 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.
  2. [Section 6, Table 3] 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.
  3. [Section 6] 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.
  4. [Algorithms 3 and 4, line 14] 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.
  5. [Various] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: ParAC's contribution is a parallel scheduling and implementation layer over the external AC algorithm; no fitted parameter is renamed as a prediction and no load-bearing claim reduces to a self-citation.

full rationale

The paper's derivation chain is inherited, not internally circular. ParAC implements the sequential randomized AC factorization (Kyng-Sachdeva; Gao-Kyng-Spielman) and contributes dynamic dependency counting, memory management, and CPU/GPU scheduling. The property E(GG^T)=L is cited to [23,37], which is external to this author set, so the statistical foundation is independent support rather than a self-referential loop. The dynamic readiness rule 'dp[i]=0' is a control-flow definition of the implemented schedule, not a derived prediction that is then validated against the same definition; the paper does not fit any parameter and then report that parameter as a discovered result. Self-citations (RCHOL [10], GPTune [11-13], and [40]) are used for contrast, background, or future-work suggestions and do not carry the proof of ParAC's correctness. The manuscript does contain an unproven invariant: Section 4.2 asserts that the direct one-hop dependency count 'is still guaranteed' to govern safe elimination, and Section 7.1 explicitly leaves a theoretical analysis of the achieved parallelism open. That is a missing-proof and correctness-risk issue, not circularity. The schedule is defined by the count, and whether it coincides exactly with sequential AC's elimination order is an empirical and open theoretical question, not an equivalence the paper supplies by construction. The central claims are benchmarked against external solvers (Hypre, AmgX, cuSPARSE ichol), and the results are not forced by definition or by self-citation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper contributes engineering and scheduling on top of the known AC algorithm. Its correctness rests on prior results (AC expectation property, Rose-Tarjan dependencies) and on an unproven dynamic dependency counting mechanism.

assumptions (4)
  • standard math Rose-Tarjan characterization of elimination dependencies in classical Cholesky: vertex i depends on j iff j<i and there is a path from i to j whose intermediate vertices all have labels < i.
    Invoked in Lemma 4.1 to argue which vertices must be eliminated before another in classical Cholesky; the paper extends this intuition to randomized elimination.
  • domain assumption The randomized AC algorithm preserves the expectation E[GG^T]=L, and sorting neighbors by edge weight improves numerical quality.
    ParAC inherits these properties from AC; the paper relies on the AC algorithm being a valid preconditioner, citing prior work.
  • ad hoc to paper Dynamic dependency counts with edge multiplicities are a sufficient condition for readiness in the random spanning-tree elimination.
    Section 4.2 and Algorithms 3/4 assume that decrementing/incrementing counts exactly captures the set of lower-labeled vertices that must be eliminated before a vertex can be processed in parallel; no formal proof is provided.
  • ad hoc to paper Processing ready vertices out of the static ordering when they are independent preserves the factorization result.
    The GPU/CPU schedulers pick any ready vertex from a queue; the paper assumes this out-of-order processing among independent vertices does not change the final factor or its preconditioning quality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners." pith.science (2026). https://pith.science/paper/5TOGHKPA

@misc{pith2026250502977,
  author       = {Pith},
  title        = {Pith review of: Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5TOGHKPA}},
  note         = {Machine review of arXiv:2505.02977}
}
read the original abstract

We introduce a parallel algorithm to construct a preconditioner for solving a large, sparse linear system where the coefficient matrix is a Laplacian matrix (a.k.a., graph Laplacian). Such a linear system arises from applications such as discretization of a partial differential equation, spectral graph partitioning, and learning problems on graphs. The preconditioner belongs to the family of incomplete factorizations and is purely algebraic. Unlike traditional incomplete factorizations, the new method employs randomization to determine whether or not to keep fill-ins, i.e., newly generated nonzero elements during Gaussian elimination. Since the sparsity pattern of the randomized factorization is unknown, computing such a factorization in parallel is extremely challenging, especially on many-core architectures such as GPUs. Our parallel algorithm dynamically computes the dependency among row/column indices of the Laplacian matrix to be factorized and processes the independent indices in parallel. Furthermore, unlike previous approaches, our method requires little pre-processing time. We implemented the parallel algorithm for multi-core CPUs and GPUs, and we compare their performance to other state-of-the-art methods.

Figures

Figures reproduced from arXiv: 2505.02977 by the authors.

Figure 1
Figure 1. An overview linking matrix sparsity, graph rep [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. A possible graph after eliminating vertex 0 in fig. 1 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Factor scaling time of three different orderings on CPU, all in seconds. We show the scaling results for all three [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Top figure shows e-tree depth using the classical e-tree computation vs. actual e-tree height vs. triangular solve critical [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 40 canonical work pages

  1. [1]

    Amestoy, Timothy A

    Patrick R. Amestoy, Timothy A. Davis, and Iain S. Duff. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm.ACM Trans. Math. Softw.30, 3 (Sept. 2004), 381–388. https://doi.org/10.1145/1024074.1024081

    arXiv 2004

  2. [2]

    Anderson, Z

    E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. 1999.LAPACK Users’ Guide(third ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA

    work page 1999

  3. [3]

    Rie Kubota Ando and Tong Zhang. 2006. Learning on graph with Laplacian regularization. InProceedings of the 20th International Conference on Neural Information Processing Systems(Canada)(NIPS’06). MIT Press, Cambridge, MA, USA, 25–32

    work page 2006

  4. [4]

    Hartwig Anzt, Edmond Chow, and Jack Dongarra. 2018. ParILUT—A new parallel threshold ILU factorization.SIAM Journal on Scientific Computing40, 4 (2018), C503–C519

    work page 2018

  5. [5]

    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. 2009. Communication-optimal parallel and sequential Cholesky decomposition. In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures. 245–252

    work page 2009

  6. [6]

    Yves Baumann and Rasmus Kyng. 2024. A Framework for Parallelizing Ap- proximate Gaussian Elimination. InProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures(Nantes, France)(SPAA ’24). As- sociation for Computing Machinery, New York, NY, USA, 195–206. https: //doi.org/10.1145/3626183.3659987

    arXiv 2024

  7. [7]

    Plemmons

    Abraham Berman and Robert J. Plemmons. 1994.Nonnegative Matrices in the Mathematical Sciences. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611971262 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611971262

    doi:10.1137/1.9781611971262 1994

  8. [8]

    Boman, Bruce Hendrickson, and Stephen Vavasis

    Erik G. Boman, Bruce Hendrickson, and Stephen Vavasis. 2008. Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners. SIAM J. Numer. Anal.46, 6 (2008), 3264–3284. https://doi.org/10.1137/040611781 arXiv:https://doi.org/10.1137/040611781

    work page doi:10.1137/040611781 2008

Show all 56 references
  1. [9]

    Boman, Sivasankaran Rajamanickam, Raymond S

    Léopold Cambier, Chao Chen, Erik G. Boman, Sivasankaran Rajamanickam, Raymond S. Tuminaro, and Eric Darve. 2020. An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations.SIAM J. Ma- trix Anal. Appl.41, 2 (2020), 715–746. https://doi.org/10.1137/19M1238...

    2020 doi

  2. [10]

    Chao Chen, Tianyu Liang, and George Biros. 2021. RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems.SIAM Journal on Scien- tific Computing43, 6 (2021), C411–C438. https://doi.org/10.1137/20M1380624 arXiv:https://doi.org/10.1137/20M1380624

    2021 doi

  3. [11]

    Y Cho, JW Demmel, G Dinh, H Luo, XS Li, Y Liu, O Marques, and WM Sid-Lakhdar

  4. [12]

    Younghyun Cho, James W Demmel, Michał Dereziński, Haoyun Li, Hengrui Luo, Michael W Mahoney, and Riley J Murray. 2023. Surrogate-based autotuning for randomized sketching algorithms in regression problems.arXiv preprint arXiv:2308.15720(2023)

    2023 arXiv

  5. [13]

    Younghyun Cho, James W Demmel, Xiaoye S Li, Yang Liu, and Hengrui Luo

  6. [14]

    Edmond Chow and Aftab Patel. 2015. Fine-grained parallel incomplete LU factorization.SIAM journal on Scientific Computing37, 2 (2015), C169–C193

    2015

  7. [15]

    M. A. Christie and M. J. Blunt. 2001. Tenth SPE Comparative Solution Project: A Comparison of Upscaling Techniques.SPE Reservoir Evaluation Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners Table 2: Convergence result for ParAC, MATLAB’s ...

    2001

  8. [16]

    2003.Efficient and portable parallel algorithms for Cholesky decomposition

    Pei Yue Liu Chu. 2003.Efficient and portable parallel algorithms for Cholesky decomposition. Lehigh University

    2003

  9. [17]

    Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford. 2018. Solving directed laplacian systems in nearly-linear time through sparse LU factorizations. In2018 IEEE 59th annual symposium on foundations of computer science (FOCS...

    2018

  10. [18]

    2006.Direct methods for sparse linear systems

    Timothy A Davis. 2006.Direct methods for sparse linear systems. SIAM

    2006

  11. [19]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. 2011. The university of Florida sparse matrix collection.ACM Trans. Math. Softw.38, 1, Article 1 (Dec. 2011), 25 pages. https: //doi.org/10.1145/2049662.2049663

    2011

  12. [20]

    Davis, Sivasankaran Rajamanickam, and Wissam M

    Timothy A. Davis, Sivasankaran Rajamanickam, and Wissam M. Sid-Lakhdar

  13. [21]

    Jim Demmel. 2012. Communication avoiding algorithms. In2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 1942–2000

    2012

  14. [22]

    James W Demmel, John R Gilbert, and Xiaoye S Li. 1999. An asynchronous parallel supernodal algorithm for sparse gaussian elimination.SIAM J. Matrix Anal. Appl.20, 4 (1999), 915–952

    1999

  15. [23]

    Yuan Gao, Rasmus Kyng, and Daniel A Spielman. 2023. Robust and practical solution of laplacian equations by approximate elimination.arXiv preprint arXiv:2303.00709(2023)

    2023 arXiv

  16. [24]

    Alan George. 1973. Nested Dissection of a Regular Finite Element Mesh. SIAM J. Numer. Anal.10, 2 (1973), 345–363. https://doi.org/10.1137/0710032 arXiv:https://doi.org/10.1137/0710032

    1973 doi

  17. [25]

    1981.Computer solution of large sparse positive definite

    Alan George and Joseph W Liu. 1981.Computer solution of large sparse positive definite. Prentice Hall Professional Technical Reference

    1981

  18. [26]

    John R. Gilbert. 1998. Combinatorial preconditioning for sparse linear systems. InSolving Irregularly Structured Problems in Parallel, Alfonso Ferreira, José Rolim, Horst Simon, and Shang-Hua Teng (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–4

    1998

  19. [27]

    Laura Grigori, James W Demmel, and Xiaoye S Li. 2007. Parallel symbolic factorization for sparse LU with static pivoting.SIAM Journal on Scientific Computing29, 3 (2007), 1289–1314

    2007

  20. [28]

    Stephen Guattery and Gary L. Miller. 1995. On the performance of spectral graph partitioning methods. InProceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms(San Francisco, California, USA)(SODA ’95). Society for Industrial and Applied Mathematics, USA, 233–242

    1995

  21. [29]

    Xiaozhe Hu and Junyuan Lin. 2024. Solving Graph Laplacians via Multilevel Sparsifiers.SIAM Journal on Scientific Computing46, 2 (2024), S378–S400. https: //doi.org/10.1137/22M1503932 arXiv:https://doi.org/10.1137/22M1503932

    2024 doi

  22. [30]

    Pierre Humbert, Batiste Le Bars, Laurent Oudre, Argyris Kalogeratos, and Nicolas Vayatis. 2021. Learning Laplacian Matrix from Graph Signals with Sparse Spectral Representation.Journal of Machine Learning Research22, 195 (2021), 1–47. http://jmlr.org/papers/v22/19-944.html

    2021

  23. [31]

    d.].hypre: High Performance Preconditioners

    hypre [n. d.].hypre: High Performance Preconditioners. https://llnl.gov/casc/ hypre, https://github.com/hypre-space/hypre

  24. [32]

    Arun Jambulapati and Aaron Sidford. 2021. Ultrasparse ultrasparsifiers and faster laplacian system solvers.ACM Transactions on Algorithms(2021)

    2021

  25. [33]

    Jones and Paul E

    Mark T. Jones and Paul E. Plassmann. 1994. Scalable iterative solution of sparse linear systems.Parallel Comput.20, 5 (May 1994), 753–773. https://doi.org/10. 1016/0167-8191(94)90004-3

    1994

  26. [34]

    David S Kershaw. 1978. The incomplete Cholesky—conjugate gradient method for the iterative solution of systems of linear equations.J. Comput. Phys.26, 1 (1978), 43–65. https://doi.org/10.1016/0021-9991(78)90098-0

    1978 doi

  27. [35]

    Kyungjoo Kim, Sivasankaran Rajamanickam, George Stelle, H Carter Edwards, and Stephen L Olivier. 2016. Task parallel incomplete cholesky factorization using 2d partitioned-block layout.arXiv preprint arXiv:1601.05871(2016)

    2016 arXiv

  28. [36]

    Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva. 2017. A framework for analyzing resparsification algorithms. InProceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms(Barcelona, Spain) (SODA ’17). Society for Industrial and Applied M...

    2017

  29. [37]

    Rasmus Kyng and Sushant Sachdeva. 2016. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 573–582

    2016

  30. [38]

    Ruipeng Li and Chaoyu Zhang. 2020. Efficient parallel implementations of sparse triangular solves for GPU architectures. InProceedings of the 2020 SIAM Conference on Parallel Processing for Scientific Computing. SIAM, 106–117

    2020

  31. [39]

    Xiaoye S. Li. 2005. An overview of SuperLU: Algorithms, implementation, and user interface.ACM Trans. Math. Softw.31, 3 (Sept. 2005), 302–325. https: //doi.org/10.1145/1089014.1089017

    2005

  32. [40]

    Tianyu Liang, Riley Murray, Aydın Buluç, and James Demmel. 2024. Fast multiplication of random dense matrices with sparse matrices. In2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 52–62. https://doi.org/10.1109/IPDPS57955.2024.00014

    2024

  33. [41]

    Joseph WH Liu. 1990. The role of elimination trees in sparse factorization.SIAM journal on matrix analysis and applications11, 1 (1990), 134–172

    1990

  34. [42]

    Duff, and Brian Vinter

    Weifeng Liu, Ang Li, Jonathan Hogg, Iain S. Duff, and Brian Vinter. 2016. A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves. InPro- ceedings of the 22nd International Conference on Euro-Par 2016: Parallel Pro- cessing - Volume 9833. Springer-Verlag, Berlin...

    2016 doi

  35. [43]

    Oren E Livne and Achi Brandt. 2012. Lean algebraic multigrid (LAMG): Fast graph Laplacian linear solver.SIAM Journal on Scientific Computing34, 4 (2012), B499–B522

    2012

  36. [44]

    M Luby. 1985. A simple parallel algorithm for the maximal independent set problem. InProceedings of the Seventeenth Annual ACM Symposium on Theory of Computing(Providence, Rhode Island, USA)(STOC ’85). Association for Comput- ing Machinery, New York, NY, USA, 1–10. https://doi...

    1985

  37. [45]

    Riley Murray, James Demmel, Michael W Mahoney, N Benjamin Erichson, Mak- sim Melnichenko, Osman Asif Malik, Laura Grigori, Piotr Luszczek, Michał Dereziński, Miles E Lopes, et al. 2023. Randomized numerical linear algebra: A perspective on the field with an eye to software.arX...

    2023 arXiv

  38. [46]

    Maxim Naumov, Marat Arsaev, Patrice Castonguay, Jonathan Cohen, Julien Demouth, Joe Eaton, Simon Layton, Nikolay Markovskiy, István Reguly, Nikolai Sakharnykh, et al. 2015. AmgX: A library for GPU accelerated algebraic multigrid and preconditioned iterative methods.SIAM Journa...

    2015

  39. [47]

    Rennich, Darko Stosic, and Timothy A

    Steven C. Rennich, Darko Stosic, and Timothy A. Davis. 2016. Accelerating sparse Cholesky factorization on GPUs.Parallel Comput.59 (2016), 140–150. https://doi.org/10.1016/j.parco.2016.06.004 Theory and Practice of Irregular Applications

    2016 doi

  40. [48]

    D. J. Rose and R. E. Tarjan. 1978. Algorithmic Aspects of Vertex Elimination of Directed Graphs.SIAM Journal on Applied MathVol. 34, No. 1 (January 1978), 176–197

    1978

  41. [49]

    2003.Iterative Methods for Sparse Linear Systems(second ed.)

    Yousef Saad. 2003.Iterative Methods for Sparse Linear Systems(second ed.). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718003 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9780898718003

    2003 doi

  42. [50]

    Sushant Sachdeva and Yibin Zhao. 2023. A simple and efficient parallel Laplacian solver. InProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures. 315–325

    2023

  43. [51]

    Daniel A Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. InProceedings of the fortieth annual ACM symposium on Theory of computing. 563–568

    2008

  44. [52]

    K. Stüben. 2001. A review of algebraic multigrid.J. Comput. Appl. Math.128, 1 (2001), 281–309. https://doi.org/10.1016/S0377-0427(00)00516-1 Numerical Analysis 2000. Vol. VII: Partial Differential Equations

    2001 doi

  45. [53]

    Nisheeth K Vishnoi et al. 2013. Lx= b.Foundations and Trends®in Theoretical Computer Science8, 1–2 (2013), 1–141

    2013

  46. [2016]

    https://api.semanticscholar.org/CorpusID:123819932

    A survey of direct methods for sparse linear systems.Acta Numerica25 (2016), 383 – 566. https://api.semanticscholar.org/CorpusID:123819932

    2016

  47. [2021]

    In2021 IEEE 14th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)

    Enhancing autotuning capability with a history database. In2021 IEEE 14th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC). IEEE, 249–257

  48. [2022]

    GPTune user guide.GPTune user guide(2022)

    2022

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.