Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Block methods — where it appears

Krylov methods that carry several starting vectors at once, so that an eigenspace of dimension d is reachable when the block is at least d wide.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

12345610⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹Ritz value, largest firstdistance from 10one vectora block of twoa space, not a ratecopies found, one vector1copies found, block of two2Krylov dimension, one vector16the second copy is not in the spaceat any number of steps

An eigenvalue one vector cannot see

A matrix with an exactly doubled eigenvalue at 10. Twelve Lanczos steps find it once; twenty-four find it once, on a Krylov space of dimension 23 in a 24-dimensional problem. A block of two vectors finds it twice. This is not slow convergence — the second copy is not in the space.

spectra · invariant subspace an eigenvalue repeated 2 times, in a 200-dimensional problemblock of 1never returns them allblock of 232 products, 16 stepsblock of 351 products, 17 stepsblock of 460 products, 15 stepsblock of 570 products, 14 stepsblock of 684 products, 14 stepsthe narrowest that workscheapest width2its products with A32the widest drawn84narrower than the multiplicity is not slowit is absent

How wide the block should be

A block narrower than the multiplicity does not converge slowly — it never returns the missing copy at all. Above the multiplicity every extra column buys iterations at about ten products with A each. And the mechanism that is supposed to make the choice unimportant never fires from a random start.

spectra · invariant subspace

Named alongside it

The objects these essays reach for when they reach for this one.

Invariant subspaceKrylov subspaceMultiplicityRitz valuesCommunicationDeflationEigenvalue gapEigenvector conditioningLanczosLanczos algorithmReorthogonalisationSynchronisation

All concepts