Gram Decay and Intrinsic Dimensions of Krylov Subspaces

ABSTRACT Krylov subspace methods solve large sparse linear systems by building a sequence of polynomial approximations to from successive matrix‐vector products. In finite precision, the number of numerically independent directions that can be extracted from this sequence is bounded by the intrinsic information dimension , defined as the index at which the Krylov basis matrix becomes numerically rank‐deficient: , where is the accumulated finite‐precision noise floor. For sequences of elliptic PDE discretizations with spectral density, the normalized Gram matrix of any Chebyshev basis block decays off‐diagonal at a rate , established via two integrations by parts applied to the Chebyshev moment integral; this gives (monomial basis) or (Chebyshev basis), where is the spectral condition number. Two consequences follow directly from this bound. First, any restarted Krylov method requires restart length – to reproduce unrestarted convergence; the common choices or produce 8– overhead or practical stagnation for . Second, ‐step GCR with Chebyshev basis and Forward Gauss–Seidel Gram solve requires only blocks of inter‐block orthogonalization history, achieving storage and global synchronizations per iteration independent of iteration count; the 20– gap between this truncation depth and the restart minimum is explained by the same decay rate.