Storage requirements

This section provides the storage requirements of all Krylov methods available in Krylov.jl.

Notation

We denote by $m$ and $n$ the number of rows and columns of the linear problem. The memory parameter of DIOM, FOM, DQGMRES, GMRES, FGMRES and GPMR is $k$. The numbers of shifts of CG-LANCZOS-SHIFT is $p$.

Theoretical storage requirements

The following tables provide the number of coefficients that must be allocated for each Krylov method. The coefficients have the same type as those that compose the linear problem we seek to solve. Each table summarizes the storage requirements of Krylov methods recommended to a specific linear problem.

Hermitian positive definite linear systems

MethodsCGCRCARCG-LANCZOSCG-LANCZOS-SHIFT
Storage$4n$$5n$$7n$$5n$$3n + 2np + 5p$

Hermitian indefinite linear systems

MethodsSYMMLQMINRESMINRES-QLPMINARES
Storage$5n$$6n$$6n$$8n$

Non-Hermitian square linear systems

MethodsCGSBICGSTABBiLQQMR
Storage$6n$$6n$$8n$$9n$
MethodsDIOMDQGMRES
Storage$n(2k+1) + 2k - 1$$n(2k+2) + 3k + 1$
MethodsFOMGMRESFGMRES
Storage$\dfrac{}{}$$\!n(2+k) +2k + \dfrac{k(k + 1)}{2}\!$$\!n(2+k) + 3k + \dfrac{k(k + 1)}{2}\!$$\!n(2+2k) + 3k + \dfrac{k(k + 1)}{2}\!$

Least-norm problems

MethodsUSYMLQCGNECRMRLNLQCRAIGCRAIGMR
Storage$5n + 3m$$3n + 2m$$3n + 2m$$3n + 4m$$3n + 4m$$4n + 5m$

Least-squares problems

MethodsUSYMQRCGLSCRLSLSLQLSQRLSMR
Storage$6n + 3m$$3n + 2m$$4n + 3m$$4n + 2m$$4n + 2m$$5n + 2m$

Adjoint systems

MethodsBiLQRTriLQR
Storage$11n$$6m + 5n$

Saddle-point and Hermitian quasi-definite systems

MethodsTriCGTriMR
Storage$6n + 6m$$8n + 8m$

Generalized saddle-point and non-Hermitian partitioned systems

MethodGPMR
Storage$(2+k)(n+m) + 2k^2 + 11k$

Practical storage requirements

Each method has its own KrylovSolver that contains all the storage needed by the method. In the REPL, the size in bytes of each attribute and the total amount of memory allocated by the solver are displayed when we show a KrylovSolver.

using Krylov

m = 5000
n = 12000
A = rand(Float64, m, n)
b = rand(Float64, m)
solver = LsmrSolver(A, b)
show(stdout, solver, show_stats=false)
┌──────────────────┬──────────────────┬────────────────────┐
│        LsmrSolver│       nrows: 5000│        ncols: 12000│
├──────────────────┼──────────────────┼────────────────────┤
│Precision: Float64│ Architecture: CPU│Storage: 546.993 KiB│
├──────────────────┼──────────────────┼────────────────────┤
│         Attribute│              Type│                Size│
├──────────────────┼──────────────────┼────────────────────┤
│                 m│             Int64│             8 bytes│
│                 n│             Int64│             8 bytes│
│                 x│   Vector{Float64}│          93.750 KiB│
│                Nv│   Vector{Float64}│          93.750 KiB│
│               Aᴴu│   Vector{Float64}│          93.750 KiB│
│                 h│   Vector{Float64}│          93.750 KiB│
│              hbar│   Vector{Float64}│          93.750 KiB│
│                Mu│   Vector{Float64}│          39.062 KiB│
│                Av│   Vector{Float64}│          39.062 KiB│
│           err_vec│   Vector{Float64}│            40 bytes│
│             stats│LsmrStats{Float64}│            65 bytes│
└──────────────────┴──────────────────┴────────────────────┘

If we want the total number of bytes used by the solver, we can call nbytes = sizeof(solver).

nbytes = sizeof(solver)
560121

Thereafter, we can use Base.format_bytes(nbytes) to recover what is displayed in the REPL.

Base.format_bytes(nbytes)
"546.993 KiB"

To verify that we match the theoretical results, we just need to multiply the storage requirement of a method by the number of bytes associated to the precision of the linear problem. For instance, we need 4 bytes for the precision Float32, 8 bytes for precisions Float64 and ComplexF32, and 16 bytes for the precision ComplexF64.

FC = Float64                            # precision of the least-squares problem
ncoefs_lsmr = 5*n + 2*m                 # number of coefficients
nbytes_lsmr = sizeof(FC) * ncoefs_lsmr  # number of bytes
560000

Therefore, you can check that you have enough memory in RAM to allocate a KrylovSolver.

free_nbytes = Sys.free_memory()
Base.format_bytes(free_nbytes)  # Total free memory in RAM in bytes.
"13.593 GiB"
Note
  • Beyond having faster operations, using low precisions, such as simple precision, allows to store more coefficients in RAM and solve larger linear problems.
  • In the file test_allocations.jl, we use the macro @allocated to test that we match the expected storage requirement of each method with a tolerance of 2%.