My website.
In a recent post I gave intuition for the sparse Cholesky elimination tree by appealing to the task DAG and showed how it could be compressed into a tree in the sparse case. That post also showed how to use and compute the tree. Here I take a narrower and more conventional route: I start from a naive symbolic translation of right-looking Cholesky, identify the structural work it repeats, and show…
Suppose you pose the following problem to me: solve a large sparse linear system Ax=b , where A and b are public and x is unknown. Can I convince you that I have a good x without sending the whole vector? The answer turns out to be yes. I can solve the system by any method I like and send a proof whose validator uses only a few megabytes of memory, even when the solution has millions of entries.…
Here I preview RatchesQR (note: contact me directly for access I have made the repository private to avoid LLM scraping without attribution) , a low-memory sparse QR-factorization-based preconditioner that achieves good preconditioned GMRES convergence on the highly nonsymmetric test matrices below, with a static execution graph and no numerical pivoting. I have been exploring ways to use bytes…
I present here a deliberately unpleasant family for sparse linear solvers that operate only on an input sparse matrix. This counter-example is closely related to the nightmare matrices of a previous post , but with a key strengthening: the matrices I present here will be symmetric and positive definite (“SPD” for short). In my prior post I relied on indefiniteness of the matrix to make iterative…
In my recent post I motivated the elimination tree and gave a loose derivation from the Cholesky task DAG. I thought it might be nice to visualize the actual tree-computation algorithm (without path compression) to help develop intuition for how it represents structural fill so compactly. I asked Codex to build this visualization, which I share below: Open the elimination tree visualization You…
Here I derive the elimination tree for the right-looking sparse Cholesky algorithm, computing A = LL^T for a lower triangular L and sparse symmetric positive definite A . Elimination trees also appear throughout sparse LU and QR software, though those factorizations require some additional machinery. For Cholesky, the tree tells us how to recover the structural fill pattern of L and compactly…
Here I simulate a roughly 4x reduction in storage for a deflation basis with almost no change in iteration count on three test problems. Packing the basis this way could reduce memory traffic and make deflation cheaper. Deflation methods allow you to precompute and store a deflation basis for a matrix A and use that stored basis to accelerate convergence on subsequent iterative solves involving A…
I explore how very small ML models might in some cases be better trained on CPU than GPU. I use the recent AdderBoard as a source for models and inspiration. In one of these I was able to achieve an approximately 8-9x per-iteration speedup on my laptop (CPU, custom C++) compared with the PyTorch A100 runs below: 17.9/2.2 for the compiled CUDA-Graphs run and 20.1/2.2 for the baseline. These are…
Here I look at “Compensated” arithmetic and its application to a small side-project CompensatedBLAS . Compensated arithmetic allows you to implement higher-accuracy accumulation using expansions of lower-precision floating-point words. Two FP32 words carry at most roughly 48 significand bits before nonoverlap and implementation losses, so they do not in general reproduce the 53-bit significand or…
I introduce a family of difficult sparse matrices (“Nightmare matrices”) \(A\) designed to frustrate several common sparse direct and iterative strategies for solving \(Ax = b\). The construction is symmetric positive semidefinite, and is positive definite when the underlying random factor has full column rank, as it did here. I then analyze the performance of Krylov methods for these matrices on…