A Randomized Algorithm for Preconditioner Selection

Conner DiPaolo; Weiqing Gu

REVIEW 3 major objections 4 minor 34 references

A Randomized Algorithm for Preconditioner Selection

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Preconditioner stability, long deemed impractical to compute, can be estimated by randomized sketching in a dimension-free number of matrix-vector products.

desk verdict A well-executed paper that makes a known trace estimator practical for preconditioner selection; the theory is mostly solid, the proxy from stability to iteration count remains unproven but the paper is honest about it. read the letter →

arxiv 1908.00633 v1 pith:NEFMG2OA submitted 2019-08-01 math.NA cs.DScs.NAstat.ML

Conner DiPaolo , Weiqing Gu This is my paper · ORCID

classification math.NAcs.DScs.NAstat.ML MSC 65F0868W2068Q1762G08

keywords preconditionerselectionstabilityrandomizedsketchingtraceestimationconjugategradientskernelregressionFrobeniusnormmatrix-vectorproductmodel

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 argues that preconditioner stability, the quantity $\|I - M^{-1}A\|_F$, is not the impractical diagnostic it was thought to be. The authors show that a randomized sketching estimator computes it, to multiplicative accuracy $\sqrt{1\pm\epsilon}$ with failure probability at most $\delta$, using $k = O(\epsilon^{-2}\log(1/\delta))$ matrix-vector products; the sample count is independent of the matrix dimension $d$. They also prove that no deterministic algorithm can do this with fewer than $d$ queries, so randomness is a necessity rather than a convenience. Because the estimate costs about as much as a constant number of conjugate-gradient iterations, selecting the best of $n$ candidate preconditioners becomes an $n$-fold repetition with a union-bound guarantee, and the method can advise using no preconditioner at all. This matters because automated, reliable preconditioner choice is a bottleneck in iterative solvers, and the paper's kernel-regression experiments show the selection rarely loses to no preconditioning.

What carries the argument

The load-bearing object is the identity $\|I - M^{-1}A\|_F^2 = \mathbb{E}\,\|(I - M^{-1}A)q\|_2^2$ for a standard Gaussian vector $q$, obtained by writing the squared Frobenius norm as a trace and using $\mathbb{E}[qq^*] = I$. This turns stability estimation into Monte Carlo trace estimation: Algorithm 1 forms $Q$ with independent scaled Gaussian columns and returns $\|(I - M^{-1}A)Q\|_F$. The analysis follows a Markov/Jensen tail bound on the quadratic form $q^*\Lambda q$, where $\Lambda$ contains the eigenvalues of $(I - M^{-1}A)^*(I - M^{-1}A)$, yielding the dimension-free sample complexity; a matching lower bound uses a one-dimensional eigenvalue perturbation and the central limit theorem. This identity is what converts matrix-vector access to $M^{-1}$ and $A$ -- exactly the access iterative solvers already provide -- into a certificate of preconditioner quality.

What would settle it

Take $A = I - e_1e_1^T$ and $M = I$, the worst case used in Theorem 2.4, and run Algorithm 1 with $k = \lfloor 4\epsilon^{-2}\log(1/\sqrt{8\pi}\delta) - 2\epsilon^{-2}\log\log(1/\sqrt{8\pi}\delta)\rfloor$ for small $\epsilon$; if the estimate falls outside $\sqrt{1\pm\epsilon}\,\|I - M^{-1}A\|_F$ with probability less than $\delta$ over many trials, the claimed tightness bound is violated. Separately, finding a positive-definite matrix and a set of preconditioners whose stability ordering is opposite to their conjugate-gradient iteration ordering would refute the proxy on which the selection method rests.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the Frobenius-norm stability $\|I - M^{-1}A\|_F$, long regarded as impractical to compute, is efficiently estimable and sufficient to drive preconditioner selection. Algorithm 1 draws $k$ independent Gaussian vectors $q_i$, forms the sketch $S = (I - M^{-1}A)Q$, and returns $\|S\|_F$; Theorem 2.2 guarantees that with $k \ge \frac{12}{\epsilon^2(3-2\epsilon)}\log\frac{2}{\delta}$ this estimate lies within $\sqrt{1\pm\epsilon}$ of the true stability with probability at least $1-\delta$. The authors prove this bound is asymptotically tight, with leading constant $4$ as $\epsilon\to 0$, using a central-limit argument that also confirms a known conjecture about Gaussian trace estimators. Algorithm 2 then estimates stability for every candidate and returns the minimum; with $k = O(\epsilon^{-2}\log(n/\delta))$ it returns a preconditioner within $\sqrt{(1+\epsilon)/(1-\epsilon)}$ of the minimal stability, with probability $1-\delta$. The paper further proves a deterministic lower bound that any exact multiplicative approximation requires at least $d$ matrix-vector queries, and an anti-concentration speedup that decouples the number of candidates from the accuracy cost when there is a clear winner.

Load-bearing premise

The load-bearing premise is that minimizing $\|I - M^{-1}A\|_F$ reliably identifies the preconditioner that minimizes conjugate-gradient iterations; the paper relies on empirical evidence for this proxy, tests it in its experiments, and does not prove it, and its own oilpan result shows that increasing the sketch size can move the selected preconditioner away from the minimal-iteration choice.

Editorial extensions

If this is right

A solver can screen all candidates in advance because each stability estimate costs about as much as a constant number of preconditioned conjugate-gradient iterations.
No deterministic algorithm can certify stability with fewer than $d$ matrix-vector products, so the randomized failure probability is unavoidable.
For $n$ candidates, $k = O(\epsilon^{-2}\log(n/\delta))$ matrix-vector products per candidate suffices to return a preconditioner within $\sqrt{(1+\epsilon)/(1-\epsilon)}$ of minimal stability with probability $1-\delta$.
The method can return the identity as the selected preconditioner, giving a principled recommendation to skip preconditioning when no candidate beats doing nothing; in the paper's kernel-regression tests this never produced more conjugate-gradient iterations than no preconditioner.
When candidate stabilities are well separated, the algorithm can prune bad candidates early and decouple the number of candidates from the accuracy cost, reducing the total work to a sum dominated by the near-ties.

Reading between the lines

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

If stability becomes cheap enough to evaluate repeatedly, one could re-select or re-weight preconditioners online during a single solve; the paper does not explore this adaptive use, but its per-query cost makes it plausible.
The same dimension-free estimator applies to any matrix $B$ given by matrix-vector access, not only $I - M^{-1}A$, which suggests cheap diagnostics for other matrix functions used in numerical linear algebra.
The anti-concentration speedup suggests a practical adaptive protocol: start with a small sketch, prune obviously bad candidates, and spend larger sketch sizes only on the finalists; the paper proves the bound under a distributional condition but does not separately validate this protocol as an algorithm.
Because the estimator parallelizes down to one matrix-vector product per processor, it could serve as a distributed preconditioner-selection primitive for very large systems; the paper notes the trivial parallelization but leaves communication-aware analyses open.

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.

Desk Editor's Note

read the letter

Here's my take. The paper does one genuinely new thing and does it well: it points out that preconditioner stability can be estimated with a Gaussian trace estimator in O(k) matrix-vector products, and proves a deterministic query lower bound that shows this kind of claim is close to optimal. The lower bound is simple but clean, and the sample-complexity analysis (Theorem 2.2) is a nice repurposing of known results with an improved constant. The experiments, especially the kernel regression ones, are suggestive and honest: they report cases where larger sketch size makes the selection worse, and they explicitly say the stability proxy is not perfect.

The soft spots are real but not fatal. First, the theorem statements have a few warts. The simplified k bound in Theorem 2.2 does not seem to follow from the displayed bound when epsilon = 1/2, and the formula in Theorem 2.4 has ambiguous logarithms and a floor that complicates the asymptotic story. These are the kinds of things a referee should ask to be cleaned up, not reasons to reject.

Second, and more importantly, the paper's advertised conclusion—that selecting minimal stability gives a good CG preconditioner—is not proven. The stress-test example is right: for M = alpha A, every alpha gives M^{-1}A proportional to I, so CG converges in one step, while ||I - M^{-1}A||_F varies. So stability can rank equivalent preconditioners. The paper itself acknowledges this in Section 4 and in the oilpan discussion, so it is not hiding the limitation. But the abstract's 'never worse' claim in kernel regression is an empirical observation from single runs with no released code or data, so I'd want to see that reproduced and ideally replaced by a distributional claim or a worst-case bound.

Overall, the core contribution—an efficient, provably accurate estimator for a practically meaningful quantity—holds up. The gap between stability and iteration count is real but clearly documented, and the paper does not overclaim. I'd send this to a serious referee; the math is solid enough to engage with, and the application area is of interest to a broad numerical linear algebra audience. After some revision to fix the theorem statements and provide code/data, it could be accepted.

Referee Report

3 major / 4 minor

Summary. The paper studies the preconditioner-selection problem: given candidate preconditioners M_j for Ax=b, choose the one that minimizes the number of conjugate-gradient iterations. The core algorithmic contribution is a randomized estimator Stab(A,M,k) of the preconditioner stability ||I-M^{-1}A||_F, obtained by applying the Gaussian trace estimator to the matrix (I-M^{-1}A)^*(I-M^{-1}A). The paper proves a deterministic lower bound (Theorem 2.1), a sample-complexity bound for the estimator (Theorem 2.2), a selection guarantee for choosing a near-minimal-stability candidate among n preconditioners (Theorem 2.3), a tightness result for the leading constant (Theorem 2.4), and an accelerated variant under an anti-concentration condition (Theorem 2.5). The numerical section evaluates stability-based selection on SuiteSparse matrices and on kernel-regression systems, and reports a kernel-regression preconditioning method that never uses more CG iterations than no preconditioner in the tested parameter range.

Significance. If the technical claims are repaired, the paper makes a useful point: a quantity previously considered impractical to compute can be estimated with O(epsilon^-2 log(1/delta)) matrix-vector products, independent of dimension. The deterministic lower bound in Theorem 2.1 is a clean and interesting argument, and the estimator is extremely simple and trivially parallelizable. The experiments are extensive and the kernel-regression results are genuinely promising. However, the practical interpretation of the method as a CG-preconditioner selector depends on the unproved premise that minimizing ||I-M^{-1}A||_F minimizes CG iterations; the paper itself identifies this as an open problem and reports an instance where the proxy is imperfect. The theorem statements also contain several errors that must be fixed before the results can be relied upon.

major comments (3)

[Sections 3.1.1 and 4; Theorem 2.3] The selection guarantee in Theorem 2.3 is only a guarantee about the stability functional ||I-M^{-1}_j A||_F, not about the number of CG iterations. The abstract and the experimental discussion, however, present the method as selecting the preconditioner that minimizes iterations. This extra step is not proved: Section 4 explicitly lists the fundamental limits of the stability proxy as an open problem, and Section 3.1.1 reports that for the oilpan matrix, increasing k from 10 to 50 moves the selected preconditioner away from the iteration-minimal one. One can also see the mathematical mismatch in the simplest SPD case: for M=alpha A, M^{-1}A=alpha^{-1}I has condition number 1, so exact-arithmetic CG takes one iteration for every alpha, while ||I-M^{-1}A||_F = sqrt(d)|1-alpha^{-1}| varies with alpha. The practical claims should be reframed as empirical, or a supporting result connecting stability to iteration counts should be supplied.
[Theorem 2.2] The statement and proof of Theorem 2.2 have two problems. First, the displayed sufficient condition is k >= 12/(epsilon^2(3-2epsilon)) log(2/delta); for epsilon <= 1/2 this gives at best k >= 6/epsilon^2 log(2/delta), not k >= 6/epsilon^2 log(1/delta) as claimed in the 'In particular' sentence. The stated simplification understates the proven sample size by a log 2 factor. Second, the theorem is stated for all 0<epsilon<1, but the lower-tail argument chooses t = epsilon/(2(1-epsilon)), which exceeds 1/2 when epsilon>1/2; the MGF bound (1-2t)^{-k/2} used in the proof is not valid in that range. Since all later applications use epsilon<=1/2, the main use of the theorem survives, but the theorem as stated is not proved.
[Theorem 2.4] The explicit formula for k in Theorem 2.4 is not correctly derived from the proof. The proof sets k = floor(2/epsilon^2 W(1/(8 pi delta^2))). Using W(x) >= log x - log log x gives k >= floor(4 epsilon^{-2} log(1/(sqrt(8 pi) delta)) - 2 epsilon^{-2} log log(1/(sqrt(8 pi) delta)) - 2 epsilon^{-2} log 2). The theorem omits the final -2 epsilon^{-2} log 2 term. Since the failure probability decreases as k increases, choosing a k larger than the threshold established by the proof is in the wrong direction for a guaranteed lower bound on the failure probability. The statement and its proof need to be reconciled; as written, the claimed tightness result is not established.

minor comments (4)

[Theorem 2.2 proof] The proof states that Stab(A,M,k) is equal in distribution to (1/k) sum_{i=1}^k q_i^* Lambda q_i; this is true of the squared estimator Stab(A,M,k)^2, not of Stab itself. The surrounding inequalities concern the squared quantity, so the wording should be corrected.
[Equations (2.11)-(2.12)] The letter m appears in the exponents in Equations (2.11)-(2.12) but is never defined; it should be k.
[Theorem 2.3] The simplified bound k >= 11/epsilon^2 log(2n/delta) leading to a (1+epsilon)-factor is asserted without showing the intermediate scalar inequalities. Since the derivation involves choosing an effective accuracy different from epsilon, a sentence or displayed calculation is needed.
[Various] There are several typographical and presentation issues: 'Tyrtyshkinov' is misspelled in Algorithm 2, 'standarad' appears in Section 3.2.1, and Figure 1 relies on color alone to convey positive versus negative values; a grayscale-accessible encoding would improve the paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the stability estimator is a direct trace identity, the lower bounds are self-contained, and the proxy caveat is an empirical limitation, not a circular derivation.

full rationale

The paper's central derivation is self-contained rather than circular. Algorithm 1 estimates ||I - M^{-1}A||_F via the exact identity ||I - M^{-1}A||_F^2 = E||(I - M^{-1}A)q||_2^2 for standard Gaussian q (Eqs. 2.2-2.5), so the estimator is not defined in terms of its own output. The deterministic lower bound (Theorem 2.1) is proved directly by constructing two matrices that are indistinguishable to any deterministic algorithm, and the randomized upper bounds (Theorems 2.2-2.3) follow from standard moment-generating-function and union-bound arguments, with no fitted parameter renamed as a prediction. The paper explicitly disclaims novelty of the estimator's mathematical core: 'It is important to note that the mathematical foundations of the above algorithm are not novel. It is equivalent in exact arithmetic to applying the trace estimators in [25]', which is an external reference, not a self-citation. References [5] and [33] are by other authors, and the paper's claimed optimality result is proved internally rather than imported from same-author work. The practical premise that ||I - M^{-1}A||_F forecasts conjugate-gradient iteration counts is presented as a cited empirical proxy, and Section 3.1.1 openly reports that increasing k can move the selected preconditioner away from the minimal-iteration choice for the oilpan matrix. That is a limitation or correctness risk, not circularity, because the theorems do not define the target quantity in terms of the proxy; they establish approximation guarantees relative to the stability objective itself. No step in the derivation chain reduces by construction to its own inputs.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new physical or mathematical entities are introduced; the estimator uses existing Gaussian sketches and the stability measure is from prior literature.

free parameters (3)

sketch size k in experiments = 10 or 50
User-chosen accuracy/effort hyperparameter in Algorithm 1; the theoretical guarantees hold for any k. Not fitted to data.
low-rank rank r = 25
Hand-chosen rank for the geometric kernel preconditioner in Section 3.2. Not fitted to data.
number of k-means clusters c = ceil(sqrt(d))
Hand-chosen cluster count for reordering kernel data. Not fitted to data.

assumptions (5)

domain assumption The matrix-vector product access model: algorithms may query (M^{-1}q, Aq) but cannot inspect entries of A or M.
Used in Theorem 2.1 to define the deterministic lower bound and in Algorithm 1's complexity model. If direct entry access were allowed, deterministic algorithms could be possible.
domain assumption Preconditioner stability ||I-M^{-1}A||_F is a meaningful proxy for iterative solver iteration count.
The entire selection method aims to minimize this proxy; the paper cites [8] and tests it empirically, but provides no theorem connecting stability to CG iterations. The oilpan case in Section 3.1 shows the proxy is imperfect.
standard math Rotation invariance of standard Gaussian vectors.
Used in Theorem 2.2 to replace (I-M^{-1}A)q by Lambda^{1/2} q after unitary diagonalization.
standard math Tail bounds and moment generating functions for chi-square and Gaussian variables.
Used in Theorems 2.2 and 2.4 to derive sample-complexity bounds and the tightness result.
ad hoc to paper Anti-concentration condition F(t) <= c t in Theorem 2.5.
This is an assumption about the input stability distribution that is not generally guaranteed; it is used only for the improved runtime of Algorithm 3, not for Algorithm 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Randomized Algorithm for Preconditioner Selection." pith.science (2026). https://pith.science/paper/NEFMG2OA

@misc{pith2026190800633,
  author       = {Pith},
  title        = {Pith review of: A Randomized Algorithm for Preconditioner Selection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NEFMG2OA}},
  note         = {Machine review of arXiv:1908.00633}
}

abstract

The task of choosing a preconditioner $\boldsymbol{M}$ to use when solving a linear system $\boldsymbol{Ax}=\boldsymbol{b}$ with iterative methods is difficult. For instance, even if one has access to a collection $\boldsymbol{M}_1,\boldsymbol{M}_2,\ldots,\boldsymbol{M}_n$ of candidate preconditioners, it is currently unclear how to practically choose the $\boldsymbol{M}_i$ which minimizes the number of iterations of an iterative algorithm to achieve a suitable approximation to $\boldsymbol{x}$. This paper makes progress on this sub-problem by showing that the preconditioner stability $\|\boldsymbol{I}-\boldsymbol{M}^{-1}\boldsymbol{A}\|_\mathsf{F}$, known to forecast preconditioner quality, can be computed in the time it takes to run a constant number of iterations of conjugate gradients through use of sketching methods. This is in spite of folklore which suggests the quantity is impractical to compute, and a proof we give that ensures the quantity could not possibly be approximated in a useful amount of time by a deterministic algorithm. Using our estimator, we provide a method which can provably select the minimal stability preconditioner among $n$ candidates using floating point operations commensurate with running on the order of $n\log n$ steps of the conjugate gradients algorithm. Our method can also advise the practitioner to use no preconditioner at all if none of the candidates appears useful. The algorithm is extremely easy to implement and trivially parallelizable. In one of our experiments, we use our preconditioner selection algorithm to create to the best of our knowledge the first preconditioned method for kernel regression reported to never use more iterations than the non-preconditioned analog in standard tests.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 31 canonical work pages

[1]

Arthur and S

D. Arthur and S. V assilvitskii , k-means++: The advantages of careful seeding , in Proceed- ings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, pp. 1027–1035

work page 2007
[2]

Asuncion and D

A. Asuncion and D. Newman , Uci machine learning repository , 2007

work page 2007
[3]

A vron, K

H. A vron, K. L. Clarkson, and D. P. Woodruff , Faster kernel ridge regression using sketching and preconditioning , SIAM Journal on Matrix Analysis and Applications, 38 (2017), pp. 1116–1138

work page 2017
[4]

A vron, A

H. A vron, A. Druinsky, and S. Toledo , Spectral condition-number estimation of large sparse matrices, Numerical Linear Algebra with Applications, 26 (2019), p. e2235

work page 2019
[5]

A vron and S

H. A vron and S. Toledo , Randomized algorithms for estimating the trace of an implicit symmetric positive semi-deﬁnite matrix , Journal of the ACM (JACM), 58 (2011), p. 8

work page 2011
[6]

Axelsson and V

O. Axelsson and V. Eijkhout , Vectorizable preconditioners for elliptic diﬀerence equations in three space dimensions, in Advances in Parallel Computing, vol. 1, Elsevier, 1990, pp. 299– 321

work page 1990
[7]

Benzi , Preconditioning techniques for large linear systems: a survey , Journal of computa- tional Physics, 182 (2002), pp

M. Benzi , Preconditioning techniques for large linear systems: a survey , Journal of computa- tional Physics, 182 (2002), pp. 418–477

work page 2002
[8]

Benzi, D

M. Benzi, D. B. Szyld, and A. V an Duin , Orderings for incomplete factorization precon- ditioning of nonsymmetric problems , SIAM Journal on Scientiﬁc Computing, 20 (1999), pp. 1652–1670

work page 1999

Show all 34 references

[9]

Bhatia, Positive deﬁnite matrices , vol

R. Bhatia, Positive deﬁnite matrices , vol. 16, Princeton university press, 2009

2009
[10]

Chow and Y

E. Chow and Y. Saad , Experimental study of ilu preconditioners for indeﬁnite matrices , Journal of Computational and Applied Mathematics, 86 (1997), pp. 387–414

1997
[11]

Cutajar, M

K. Cutajar, M. Osborne, J. Cunningham, and M. Filippone , Preconditioning kernel ma- trices, in International Conference on Machine Learning, 2016, pp. 2529–2538

2016
[12]

Cuthill and J

E. Cuthill and J. McKee , Reducing the bandwidth of sparse symmetric matrices, in Proceed- ings of the 1969 24th national conference, ACM, 1969, pp. 157–172. A RANDOMIZED ALGORITHM FOR PRECONDITIONER SELECTION 21

1969
[13]

T. A. Davis and Y. Hu , The University of Florida sparse matrix collection, ACM Transactions on Mathematical Software (TOMS), 38 (2011), p. 1

2011
[14]

Deift and T

P. Deift and T. Trogdon , The conjugate gradient algorithm on well-conditioned wishart matrices is almost deteriministic , arXiv preprint arXiv:1901.09007, (2019)

2019 arXiv
[15]

I. S. Duff and G. A. Meurant , The eﬀect of ordering on preconditioned conjugate gradients, BIT Numerical Mathematics, 29 (1989), pp. 635–657

1989
[16]

G. H. Golub and C. F. V an Loan , Matrix computations, vol. 3, JHU Press, 2012

2012
[17]

R. D. Gordon , Values of mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument, The Annals of Mathematical Statistics, 12 (1941), pp. 364–366

1941
[18]

Halko, P.-G

N. Halko, P.-G. Martinsson, and J. A. Tropp , Finding structure with randomness: Proba- bilistic algorithms for constructing approximate matrix decompositions , SIAM review, 53 (2011), pp. 217–288

2011
[19]

Hoorfar and M

A. Hoorfar and M. Hassani , Approximation of the Lambert- W function and hyperpower function, Research report collection, 10 (2007)

2007
[20]

Jamieson, M

K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck , On ﬁnding the largest mean among many, arXiv preprint arXiv:1306.3917, (2013)

2013 arXiv
[21]

R. B. Lehoucq, D. C. Sorensen, and C. Yang , ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods , vol. 6, Siam, 1998

1998
[22]

Y. Li, H. L. Nguyen, and D. P. Woodruff , On sketching matrix norms and the top singu- lar vector, in Proceedings of the twenty-ﬁfth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2014, pp. 1562–1581

2014
[23]

Pagh , Compressed matrix multiplication , ACM Transactions on Computation Theory (TOCT), 5 (2013), p

R. Pagh , Compressed matrix multiplication , ACM Transactions on Computation Theory (TOCT), 5 (2013), p. 9

2013
[24]

Rahimi and B

A. Rahimi and B. Recht , Random features for large-scale kernel machines , in Advances in neural information processing systems, 2008, pp. 1177–1184

2008
[25]

Roosta-Khorasani and U

F. Roosta-Khorasani and U. Ascher , Improved bounds on sample size for implicit matrix trace estimators, Foundations of Computational Mathematics, 15 (2015), pp. 1187–1212

2015
[26]

A. Rudi, D. Calandriello, L. Carratino, and L. Rosasco , On fast leverage score sam- pling and optimal learning , in Advances in Neural Information Processing Systems, 2018, pp. 5672–5682

2018
[27]

A. Rudi, L. Carratino, and L. Rosasco , Falkon: An optimal large scale kernel method , in Advances in Neural Information Processing Systems, 2017, pp. 3888–3898

2017
[28]

D. C. Sorensen , Implicitly restarted arnoldi/lanczos methods for large scale eigenvalue calcu- lations, in Parallel Numerical Algorithms, Springer, 1997, pp. 119–165

1997
[29]

L. N. Trefethen and D. Bau III , Numerical linear algebra, vol. 50, Siam, 1997

1997
[30]

E. E. Tyrtyshnikov , Optimal and superoptimal circulant preconditioners , SIAM Journal on Matrix Analysis and Applications, 13 (1992), pp. 459–473

1992
[31]

Vershynin , High-dimensional probability: An introduction with applications in data sci- ence, vol

R. Vershynin , High-dimensional probability: An introduction with applications in data sci- ence, vol. 47, Cambridge University Press, 2018

2018
[32]

C. K. Williams and C. E. Rasmussen , Gaussian processes for machine learning , vol. 2, MIT Press Cambridge, MA, 2006

2006
[33]

Wimmer, Y

K. Wimmer, Y. Wu, and P. Zhang , Optimal query complexity for estimating the trace of a matrix, in International Colloquium on Automata, Languages, and Programming, Springer, 2014, pp. 1051–1062

2014
[34]

D. P. Woodruff , Sketching as a tool for numerical linear algebra , Foundations and Trends® in Theoretical Computer Science, 10 (2014), pp. 1–157

2014

Pith tools

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

[1] [1]

Arthur and S

D. Arthur and S. V assilvitskii , k-means++: The advantages of careful seeding , in Proceed- ings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, pp. 1027–1035

work page 2007

[2] [2]

Asuncion and D

A. Asuncion and D. Newman , Uci machine learning repository , 2007

work page 2007

[3] [3]

A vron, K

H. A vron, K. L. Clarkson, and D. P. Woodruff , Faster kernel ridge regression using sketching and preconditioning , SIAM Journal on Matrix Analysis and Applications, 38 (2017), pp. 1116–1138

work page 2017

[4] [4]

A vron, A

H. A vron, A. Druinsky, and S. Toledo , Spectral condition-number estimation of large sparse matrices, Numerical Linear Algebra with Applications, 26 (2019), p. e2235

work page 2019

[5] [5]

A vron and S

H. A vron and S. Toledo , Randomized algorithms for estimating the trace of an implicit symmetric positive semi-deﬁnite matrix , Journal of the ACM (JACM), 58 (2011), p. 8

work page 2011

[6] [6]

Axelsson and V

O. Axelsson and V. Eijkhout , Vectorizable preconditioners for elliptic diﬀerence equations in three space dimensions, in Advances in Parallel Computing, vol. 1, Elsevier, 1990, pp. 299– 321

work page 1990

[7] [7]

Benzi , Preconditioning techniques for large linear systems: a survey , Journal of computa- tional Physics, 182 (2002), pp

M. Benzi , Preconditioning techniques for large linear systems: a survey , Journal of computa- tional Physics, 182 (2002), pp. 418–477

work page 2002

[8] [8]

Benzi, D

M. Benzi, D. B. Szyld, and A. V an Duin , Orderings for incomplete factorization precon- ditioning of nonsymmetric problems , SIAM Journal on Scientiﬁc Computing, 20 (1999), pp. 1652–1670

work page 1999