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. It is an explicit tradeoff where we accept an upfront computational cost (subspace computation, usually an eigensolver) as well as additional memory footprint and memory traffic on subsequent iterations, since every iteration of a deflation method will require us to read the deflation vectors at least once.
I demonstrate my methodology and results below
Using my Krylov-bits library I formed indefinite sparse matrices of the following form (with different mx,my)
mx=32
my=32
m=mx*my
bands = [0,1,mx]
A = sp.diags([rng.uniform(-1,1,size=m) for _ in bands],bands,shape=(m,m))
#Symmetrize
A = A + A.T
Here sp denotes scipy.sparse, and symmetrization also doubles the sampled diagonal. The matrices in the runs below are indefinite.
In each case I precomputed a deflation set whose dimension is approximately 5% of the matrix dimension:
| mx=my | n=mx*my | Deflation subspace size k |
|---|---|---|
| 32 | 1024 | 51 |
| 64 | 4096 | 205 |
| 128 | 16384 | 819 |
Next I solve a linear system using MINRES without deflation, with deflation, and then with deflation after clearing low mantissa bits. I record iteration counts, relative residuals, and relative errors against the known solution used to construct the right-hand side. The arithmetic remains FP64; only the stored basis values are quantized. With 4 kept mantissa bits, the proposed packed representation would use 16 bits per entry and therefore one quarter of the storage of the original basis because
fp64 = 1 sign bit + 11 exponent bits + 52 mantissa bits
packed_deflation_format = 1 sign bit + 11 exponent bits + 4 mantissa bits
I do not actually pack these fields into a 16-bit integer, so these results test the numerical effect of quantization rather than its performance benefit.
| Run | Kept mantissa bits | MINRES iterations | Relative residual | Relative error |
|---|---|---|---|---|
| Plain MINRES | 52 | 1490 | 6.088e-07 | 3.113e-03 |
| Deflated MINRES, unquantized basis | 52 | 254 | 3.592e-07 | 2.775e-06 |
| Deflated MINRES, quantized basis | 4 | 260 | 3.671e-07 | 3.387e-06 |
| Deflated MINRES, quantized basis | 1 | 372 | 9.465e-07 | 2.120e-04 |
| Run | Kept mantissa bits | MINRES iterations | Relative residual | Relative error |
|---|---|---|---|---|
| Plain MINRES | 52 | 6285 | 1.296e-06 | 7.321e-04 |
| Deflated MINRES, unquantized basis | 52 | 300 | 6.520e-07 | 6.050e-06 |
| Deflated MINRES, quantized basis | 4 | 300 | 6.622e-07 | 6.158e-06 |
| Run | Kept mantissa bits | MINRES iterations | Relative residual | Relative error |
|---|---|---|---|---|
| Plain MINRES | 52 | 9658 | 1.939e-06 | 8.364e-03 |
| Deflated MINRES, unquantized basis | 52 | 326 | 1.525e-06 | 1.374e-05 |
| Deflated MINRES, quantized basis | 4 | 327 | 1.410e-06 | 1.243e-05 |
I precomputed a deflation basis in FP64, then post hoc quantized that basis by truncating mantissa bits while preserving the FP64 sign and exponent fields. Keeping only 4 mantissa bits corresponds to a proposed 16-bit representation per basis entry, or a 4x reduction in storage relative to FP64. Across these three matrix realizations, this caused little to no degradation in the iteration count of the subsequent deflated solve. I do not expect four mantissa bits to be universally sufficient, but they worked remarkably well here. In principle, those 16 bits could be packed into an integer representation to reduce memory traffic and basis storage. Additional savings may be possible by compressing exponent information as well, for example with shared exponents over spatial blocks if the basis exhibits local correlation. The next useful experiment is an actual packed kernel with end-to-end timings.