1 History and background

The Arnoldi method is a classical iterative procedure in numerical linear algebra for approximating selected eigenvalues and eigenvectors of large matrices. It arose from the need to treat matrix problems that are too large for direct decomposition methods and too sparse to justify dense linear algebra. By working in a growing subspace rather than on the full matrix, the method offers a practical route to spectral information from only matrix-vector products.

1.1 Origins in numerical linear algebra

The method is named after Werner Arnoldi, who described the procedure in the 1950s. Its development was part of a broader effort to create algorithms that exploit structure in large linear systems and eigenvalue problems. Early work focused on reducing large matrices to smaller forms that preserve essential spectral behavior while remaining computationally manageable.

1.2 Relation to Krylov subspace methods

Arnoldi belongs to the family of Krylov subspace methods, which build approximations from repeated applications of a matrix to an initial vector. This perspective unifies many algorithms used for eigenvalue problems, linear systems, and polynomial approximation. In the Arnoldi setting, the generated subspace is orthonormalized and used to form a compact projected problem.

1.3 Development of practical implementations

In practice, the basic iteration was adapted to address storage limits and finite-precision effects. Restarted and implicitly restarted forms made the method usable for large-scale computations by controlling basis growth. These developments helped establish Arnoldi-based routines as standard tools in scientific computing software.

2 Mathematical foundations

The method is designed for matrices whose full eigenvalue decomposition is expensive or unnecessary. Its central idea is to replace the original problem with a sequence of progressively richer subspace approximations. The quality of the approximation depends on the subspace dimension, the matrix spectrum, and the starting vector.

2.1 Eigenvalue problems for large matrices

For a matrix A, the eigenvalue problem seeks scalars and vectors satisfying A x = λ x. When A is large and sparse, direct factorization or dense eigensolvers may be impractical. Iterative methods instead exploit repeated matrix-vector multiplications, which are often far cheaper than full matrix operations.

2.2 Krylov subspaces

A Krylov subspace captures information generated by powers of a matrix acting on a vector. It provides a natural space in which to search for approximate eigenvectors, especially those associated with prominent spectral components. The Arnoldi method constructs an orthonormal basis for such a space.

2.2.1 Definition of the Krylov sequence

Given a matrix A and a nonzero starting vector v, the Krylov sequence is v, A v, A^2 v, and so on. The associated Krylov subspace of order m is the span of the first m vectors in this sequence. This subspace grows as long as the new vectors add independent information.

2.2.2 Dimension growth and breakdown

The subspace dimension increases until it reaches a limit determined by linear dependence among the generated vectors. If a new vector lies entirely in the current subspace, the process encounters breakdown. In exact arithmetic, this can indicate that an invariant subspace has been captured; in finite precision, the situation may be less clear.

2.3 Orthonormal bases

To make the projected problem numerically stable, the Krylov vectors are converted into an orthonormal basis. Orthogonality reduces redundancy and improves the reliability of the smaller matrix that represents the action of A on the subspace. This basis is denoted by vectors that are mutually orthogonal and normalized.

2.3.1 Gram-Schmidt orthogonalization

The Gram-Schmidt process constructs an orthonormal set from linearly independent vectors by removing components along earlier basis vectors. In Arnoldi, each new Krylov vector is orthogonalized against the current basis. The resulting coefficients form entries of the reduced Hessenberg matrix.

2.3.2 Modified Gram-Schmidt

Modified Gram-Schmidt is a numerically preferred variant because it often behaves better in finite precision. It performs orthogonalization in a sequence that tends to reduce the accumulation of roundoff errors. For large iterative eigenvalue computations, this improvement can be significant.

3 The Arnoldi iteration

The Arnoldi iteration generates an orthonormal basis and a small upper Hessenberg matrix simultaneously. Each step expands the Krylov subspace by one dimension unless the process terminates early. The output is a compact representation of the original matrix action on the subspace.

3.1 Algorithmic procedure

The algorithm begins with a normalized starting vector and proceeds by repeated matrix-vector multiplication followed by orthogonalization. Each new vector is made orthogonal to all existing basis vectors, then normalized to become the next basis vector. The associated coefficients are stored in a small projected matrix.

3.1.1 Starting vector selection

The starting vector influences which parts of the spectrum are emphasized. In many applications it is chosen randomly or based on prior information about the problem. A well-chosen initial vector can improve convergence toward desired eigenpairs.

3.1.2 Matrix-vector multiplication step

At each iteration, the current basis vector is multiplied by the matrix A. For sparse matrices, this step is usually the dominant arithmetic cost. The method is therefore especially effective when matrix-vector products are substantially cheaper than dense matrix operations.

3.1.3 Orthogonalization against the basis

The new vector is projected onto the existing basis and the resulting components are subtracted. This removes directions already represented in the subspace and isolates the part that expands the approximation space. The coefficients obtained in this step populate the entries of the reduced matrix.

3.1.4 Construction of the Hessenberg matrix

The reduced matrix produced by Arnoldi has Hessenberg form, meaning it is upper triangular except for one subdiagonal. This structure reflects the one-step recurrence used to build the basis. The Hessenberg matrix is small enough that its eigenvalues can be computed by standard dense routines.

3.2 Arnoldi relation

The Arnoldi relation expresses the action of A on the basis in matrix form. It provides the theoretical link between the large original problem and the smaller projected problem. This relation is the foundation for extracting approximate spectral information.

3.2.1 Matrix decomposition form

If V_m is the matrix whose columns are the first m Arnoldi basis vectors, then A V_m can be written as a product involving V_m and the Hessenberg matrix, plus one additional term. This decomposition shows that the action of A on the subspace is almost closed within that subspace. The extra term accounts for the component outside the current approximation space.

3.2.2 Residual term

The residual term measures the part of A V_m that lies outside the Krylov subspace. Its size is closely related to the accuracy of Ritz approximations. When this term becomes small, the projected eigenpairs often provide good estimates of true eigenpairs of A.

3.3 Computational properties

Arnoldi is attractive because it uses matrix-vector products rather than factorization. Its efficiency depends on the sparsity pattern of the matrix and the number of iterations required. The method is therefore well suited to problems where only a few eigenpairs are needed.

3.3.1 Cost per iteration

Each iteration requires one matrix-vector multiplication and orthogonalization against the current basis. As the basis grows, the orthogonalization cost increases with the iteration count. For large m, this can become a substantial part of the total runtime.

3.3.2 Memory requirements

The algorithm stores all basis vectors accumulated so far, which can be expensive for large problems. Memory usage grows linearly with the number of iterations and the matrix dimension. This limitation is one reason restart strategies are commonly used.

4 Approximation of eigenvalues and eigenvectors

Arnoldi approximates spectral quantities by solving a small eigenvalue problem on the Krylov subspace. The resulting approximate eigenvalues and eigenvectors are called Ritz values and Ritz vectors. These approximations often converge to the most important parts of the spectrum first.

4.1 Ritz values and Ritz vectors

Ritz values are eigenvalues of the projected Hessenberg matrix, while Ritz vectors are the corresponding lifted vectors in the original space. They serve as finite-dimensional surrogates for true eigenpairs. Their accuracy improves as the subspace captures more of the relevant invariant structure.

4.1.1 Interpretation as approximations

A Ritz pair approximates an eigenpair of the original matrix when the residual is small. The projected eigenvector gives the direction in the Krylov subspace, and the eigenvalue estimates the associated spectral value. These approximations are especially useful when only a few extreme eigenvalues are needed.

4.1.2 Convergence behavior

Convergence depends on how well the Krylov subspace aligns with the desired invariant subspace. Eigenvalues that are well separated or strongly represented in the starting vector tend to converge faster. Clusters or poorly conditioned spectral regions can slow the process.

4.2 Error estimates

Error estimates help determine when an approximate eigenpair is accurate enough to stop the iteration. These estimates are usually based on residual norms and spectral separation. They provide practical stopping criteria in numerical software.

4.2.1 Residual-based bounds

The norm of the residual associated with a Ritz pair gives a direct measure of approximation quality. Small residuals indicate that the approximate vector nearly satisfies the eigenvalue equation. Bounds derived from the residual are widely used to assess convergence.

4.2.2 Separation and convergence speed

The distance between the target eigenvalue and the rest of the spectrum influences how quickly the method converges. Better-separated eigenvalues are easier to isolate in the subspace. When spectral separation is poor, more iterations may be needed.

4.3 Extraction of dominant eigenpairs

Arnoldi is often used to find dominant eigenpairs, such as those with largest magnitude or largest real part. After the projected problem is solved, the most relevant Ritz pairs are selected from the small Hessenberg eigenproblem. This approach is efficient when only a few spectral features matter.

5 Variants and extensions

The basic Arnoldi procedure is often modified to improve efficiency, target specific parts of the spectrum, or handle multiple vectors at once. These variants extend the method to a wider range of applications. They preserve the core Krylov-subspace idea while adapting the iteration strategy.

5.1 Restarted Arnoldi method

Restarting limits memory growth by periodically discarding part of the basis and continuing from a compressed representation. This makes the method practical for large-scale problems with many iterations. Restarted schemes are among the most widely used Arnoldi-based approaches.

5.1.1 Explicit restarting

Explicit restarting rebuilds the subspace after a fixed number of iterations. The process keeps selected approximate eigenvectors or other information and uses them to seed a new cycle. Although simple, it may lose useful spectral information if not designed carefully.

5.1.2 Implicitly restarted Arnoldi method

The implicitly restarted Arnoldi method refines the subspace using implicit shifts rather than a full explicit reconstruction. This technique preserves the most useful directions while filtering out unwanted ones. It is a standard choice in high-quality eigenvalue software.

5.1.3 Thick restarting

Thick restarting retains several basis vectors from the previous cycle rather than only one or two. By preserving a richer subspace, it can improve convergence for difficult problems. The approach balances memory control with spectral retention.

5.2 Shift-and-invert Arnoldi

Shift-and-invert transforms the eigenvalue problem so that selected interior eigenvalues become easier to isolate. The matrix is replaced conceptually by the inverse of a shifted matrix. This can dramatically enhance convergence for targeted spectral regions.

5.2.1 Spectral transformation

Applying a shift-and-invert transformation maps eigenvalues near the chosen shift to dominant values in the transformed problem. As a result, the Arnoldi process becomes more sensitive to the desired eigenpairs. The method is especially useful when the spectrum of interest lies away from the extremes.

5.2.2 Targeting interior eigenvalues

Interior eigenvalues are often difficult to compute directly because they are not naturally emphasized by standard Krylov growth. The transformed problem changes that ordering. This allows the algorithm to focus on eigenvalues near a specified region of the spectrum.

5.3 Block Arnoldi method

Block Arnoldi generalizes the process to multiple starting vectors at once. It is useful when several eigenpairs are sought simultaneously or when the matrix has structure that benefits from block operations. The method also helps with repeated or closely spaced eigenvalues.

5.3.1 Multiple starting vectors

Using a block of initial vectors allows the subspace to expand by several directions per iteration. This can accelerate convergence for clustered spectral features. It also supports parallel computation more naturally than a single-vector approach.

5.3.2 Deflation and dependence handling

Block methods must address linear dependence that can arise among block vectors. Deflation removes redundant directions so the basis remains numerically useful. Proper handling of dependence improves stability and prevents wasted computation.

Arnoldi is closely connected to other iterative methods in numerical linear algebra. Some of these are special cases, while others reuse the Arnoldi basis for different purposes. Together they form a large family of Krylov techniques.

6.1 Lanczos method

The Lanczos method is a specialized form of Krylov iteration for symmetric or Hermitian matrices. It uses a three-term recurrence instead of full orthogonalization. This makes it cheaper, though often more sensitive to numerical issues.

6.1.1 Symmetric-matrix specialization

For symmetric matrices, the Hessenberg matrix produced by Arnoldi reduces to a tridiagonal form in the idealized Lanczos setting. This simplification reflects the stronger structure of the matrix. It yields a more compact recurrence and lower per-step cost.

6.1.2 Loss of orthogonality considerations

In finite precision, Lanczos vectors may lose orthogonality, leading to spurious repeated eigenvalues. Arnoldi’s full orthogonalization is more robust in this respect. The comparison highlights a trade-off between efficiency and numerical stability.

6.2 GMRES

GMRES is an iterative method for solving linear systems that uses the Arnoldi basis to minimize the residual over a Krylov subspace. It is one of the most important practical uses of the Arnoldi process. The method is especially effective for nonsymmetric systems.

6.2.1 Use of Arnoldi basis in linear systems

GMRES constructs the same kind of orthonormal basis as Arnoldi. Instead of extracting eigenvalues, however, it searches for the vector in the subspace that best solves a linear equation. The shared basis construction explains the close relationship between the two methods.

6.2.2 Least-squares minimization

The reduced Hessenberg system in GMRES leads to a small least-squares problem. Solving this problem minimizes the residual norm over the current Krylov subspace. This approach gives GMRES its characteristic monotonic residual reduction in exact arithmetic.

6.3 Other Krylov subspace solvers

Many additional solvers use the Krylov framework, including methods for symmetric indefinite systems and generalized eigenproblems. These algorithms often modify the orthogonalization or recurrence structure. Arnoldi serves as a central reference point for this broader class of techniques.

7 Numerical issues

Practical implementations of Arnoldi must account for floating-point arithmetic and finite storage. These issues can affect orthogonality, convergence, and the reliability of the computed spectral data. Careful algorithm design is therefore essential.

7.1 Finite-precision effects

Roundoff errors accumulate during repeated orthogonalization and basis expansion. Over many iterations, these errors can alter the ideal mathematical behavior of the method. The effects are especially noticeable in large-scale computations.

7.1.1 Loss of orthogonality

Basis vectors that should be orthogonal may gradually become correlated due to numerical error. This loss can degrade the quality of the Hessenberg representation and the computed Ritz values. It may also cause duplicate or misleading spectral approximations.

7.1.2 Reorthogonalization strategies

One remedy is to orthogonalize a vector more than once against the current basis. Reorthogonalization improves numerical stability at additional cost. Different software packages choose different thresholds and policies depending on the problem size and desired accuracy.

7.2 Breakdown and near-breakdown

The iteration can terminate early if the new vector becomes zero or nearly zero after orthogonalization. Such events may indicate either a genuine invariant subspace or a numerical artifact. Algorithms often include safeguards to handle these cases gracefully.

7.2.1 Happy breakdown

A happy breakdown occurs when the process stops because an exact invariant subspace has been found. In this case, the current Ritz values can be especially accurate. The breakdown is “happy” because it signals successful completion rather than failure.

7.2.2 Deflation techniques

Deflation removes converged or nearly dependent directions from the active subspace. This helps keep the computation focused on unresolved spectral components. Deflation is widely used in restarted and block variants.

7.3 Storage and restart trade-offs

Long Arnoldi runs require storage of many basis vectors, which can become prohibitive. Restarting reduces memory use but may slow convergence if important information is discarded. Effective implementations balance these competing concerns.

8 Applications

The Arnoldi method is used wherever a small number of eigenpairs from a large sparse matrix are needed. Its flexibility makes it useful in engineering, physics, and computational science. Many applications rely on the method as a default eigenvalue tool.

8.1 Sparse matrix eigenvalue computation

One of the most common uses is finding extreme eigenvalues of large sparse matrices. These arise in discretized differential equations, graph problems, and optimization models. Arnoldi is well suited because it avoids dense operations.

8.2 Stability analysis

In stability studies, eigenvalues can indicate whether a system responds in a bounded or growing manner. Arnoldi helps estimate the spectral region relevant to such analyses. This is important in the study of dynamical systems and numerical schemes.

8.3 Vibrations and structural dynamics

Mechanical vibration problems often reduce to large sparse eigenvalue computations. Arnoldi is used to identify natural frequencies and mode shapes. The method supports analysis of structures where only a few low-order modes are needed.

8.4 Quantum and scientific simulation problems

In quantum mechanics and other simulation areas, large sparse operators frequently appear after discretization. Arnoldi can extract selected eigenstates or resonance information from these operators. Its iterative nature makes it suitable for high-dimensional scientific models.

9 Software implementations

Arnoldi methods are widely available in scientific computing libraries and specialized eigensolvers. Implementations vary in how they handle restarting, orthogonalization, and convergence checks. Users typically choose among them based on problem size and desired spectral targets.

9.1 Standard numerical libraries

Common linear algebra packages provide Arnoldi-based routines directly or through higher-level interfaces. These routines often expose options for shift strategies, restart parameters, and tolerance settings. They form an important part of the numerical software ecosystem.

9.2 High-performance computing considerations

On large systems, communication costs, parallel matrix-vector products, and memory bandwidth can dominate performance. Efficient Arnoldi implementations therefore pay close attention to data distribution and synchronization. Block and restarted variants can improve scalability in such environments.

9.3 Benchmarking and parameter choices

Performance depends strongly on the restart length, shift selection, and orthogonalization strategy. Benchmarks are typically used to tune these choices for a given matrix class. Good parameter selection can substantially reduce runtime without sacrificing accuracy.