Numerical methods for Data Assimilation

• Role played by large and small eigenvalues in the convergence of CG not necessarily symmetric in practice.

  • Symmetry broken for many reasons : role of clusters, role of the right-hand side. Numerous experimental evidence

  • An analysis of the convergence in terms of eigenmodes reveals classes of problems where smallest eigenmodes are difficult to capture For instance, regularized least-squares, satisfying the discrete Picard assumption (Fourier coefficients of the RHS decay faster to 0 than singular values). In this case CG even used as a regularization tool ! [P.C. Hansen, SIAM 1998]

• “Removing” the effect of small eigenvalues is often targeted

• Eigen-information (small, approximated)

• Subspace deflation technique

  • Example, , . Minimize the A-norm of the error on span( ) and solve for error equation iteratively [Frank, Vuik, 2001]

  • Or minimize the residual on to get ( ) and minimize the residual on a subspace orthogonal to [Parks, de Sturler, Mackey, Johnson and Maiti, 2004]

• Note : comparable approaches used in a restarted framework to improve the convergence for small restarts [Bjorck, Grimme, van Dooren, 1994], [Morgan,1995,2000,2002], ...

• Question 1 : Study the role of the inaccuracy in the spectral elements on the ``quality'' of the spectral preconditionners

• Question 2 : Is it possible to find criteria to screen the spectral information(keep only the relevant ones in the preconditioner)

• Question 3 : The preconditioners involve quantities such as . For large systems computing may be very expensive. What happens if we replace by

  • ( rayl. } approx.) or

  • ( eig.  approx.)

Nonlinear perturbation of an eigenvalue problem

• {Use first order perturbation theory: condition number approach

• Consider the eigenelements as the eigenelements of a perturbed matrix denoted by and . This pairs are assumed to be simple so that first order expansions of in is available (recent overview in [Stewart, 2000]).

• Compute the first order expansion in of the eigenvalues of the preconditioned matrix . is an upper-bound of

  the backward error

• .

  In particular, this does not assume any scaling on the eigenvectors

• For , is replaced by

• For , is replaced by

For , is a semi-simple eigenvalue of , with multiplicity . (Perturbation theory for semi-simple eigenvalues needed {\color{violet} [Sun, 1990]}). Furthermore

For the traditional expression is recovered

Using the orthogonality property of the eigenvectors, one may use

For , is a semi-simple eigenvalues of , with multiplicity . (Perturbation theory for semi-simple eigenvalues again needed)

Coarse space preconditioners

• 

• and   defined as previously}

For , the eigenvalues of are simple in general,

Define

• The entries of are large if some are small

• The matrices and may have large entries if some are clustered

The terms “cluster” and “small” refer respectively to the presence of cluster or of small isolated eigenvalues.

• Backward error problem :

  Let be approximate eigenpairs of .

  The backward error associated is

• Using the same rule of thumb as for linear systems,

• For the Frobenius norm, .This quantity is an upper-bound for the backward error in the spectral norm

  This can be used to get an upper-bound on the forward-error in order to screen the eigen-information

The eigenvalues of are

The first order approximation accurately approximates the computed eigenvalues

Numerical examples where the 3 smallest eigenvalues are targeted

• Distance to one

  • The exact radius

  • The computed radius

  • The estimated radius

• Some clues to analyze the results

  • : validity of the first order approximation

  • : asymptotic sensitivity

We take , , the three smallest eigenvalues of are the others are nicely located around .

We take , , the three smallest eigenvalues of $A$ are such that the 7 others are nicely located around .

• {Matrix (Harwell-Boeing)

• Symmetrically preconditioned by Incomplete Cholesky factorization (threshold )

• The right-hand side

• Stopping criterion : unpreconditioned residual norm reduced by ( )

• We take and and report the number of PCG iterations to reach convergence when the number of eigenvectors is varied