pymor.algorithms.chol_qr

Module Contents

pymor.algorithms.chol_qr.shifted_chol_qr(A, product=None, return_R=False, maxiter=3, offset=0, orth_tol=None, recompute_shift=False, check_finite=True, copy=True, product_norm=None)[source]

Orthonormalize a VectorArray using the shifted CholeskyQR algorithm.

This method computes a QR decomposition of a VectorArray via Cholesky factorizations of its Gramian matrix according to [FKN+20]. For ill-conditioned matrices, the Cholesky factorization will break down. In this case a diagonal shift will be applied to the Gramian.

  • shifted_chol_qr(A, maxiter=3, orth_tol=None) is equivalent to the shifted CholeskyQR3 algorithm (Algorithm 4.2 in [FKN+20]).

  • shifted_chol_qr(A, maxiter=np.inf, orth_tol=<some_number>) is equivalent to the shifted CholeskyQR algorithm (Algorithm 4.1 in [FKN+20]).

  • shifted_chol_qr(A, product=<some_product>, maxiter=3, orth_tol=None) is equivalent to the shifted CholeskyQR3 algorithm in an oblique inner product (Algorithm 5.1 in [FKN+20]).

Note

Note that the unshifted single iteration CholeskyQR algorithm is unstable. Setting maxiter=1 will perform the simple shifted CholeskyQR algorithm (Algorithm 2.1 in [FKN+20]) which is stable but leads to poor orthogonality in general, i.e.

\[\lVert Q^TQ - I \rVert_2 < 2,\]

(see Lemma 3.1 in [FKN+20]).

Parameters

A

The VectorArray which is to be orthonormalized.

product

The inner product Operator w.r.t. which to orthonormalize. If None, the Euclidean product is used.

return_R

If True, the R matrix from QR decomposition is returned.

maxiter

Maximum number of iterations. Defaults to 3.

offset

Assume that the first offset vectors are already orthonormal and apply the algorithm for the vectors starting at offset + 1.

orth_tol

If not None, check if the resulting VectorArray is really orthornormal and repeat the algorithm until the check passes or maxiter is reached.

recompute_shift

If False, the shift is computed just once if the Cholesky decomposition fails and reused in possible further iterations. However, the initial shift might be too large for further iterations, which would lead to a non-orthonormal basis. If True, the shift is recomputed in iterations in which the Cholesky decomposition fails. Even for an ill-conditioned A (at least for matrix condition numbers up to 10^20) is it able to compute an orthonormal basis at the cost of higher runtimes.

check_finite

This argument is passed down to SciPy linalg functions. Disabling may give a performance gain, but may result in problems (crashes, non-termination) if the inputs do contain infinities or NaNs.

copy

If True, create a copy of A instead of modifying A in-place.

product_norm

The spectral norm of the inner product. If None, it will be computed with eigs.

Returns

Q

The orthonormalized VectorArray.

R

The upper-triangular/trapezoidal matrix (if compute_R is True).