cla_utils package¶
Submodules¶
cla_utils.exercises1 module¶
- cla_utils.exercises1.ABiC(Ahat, xr, xi)[source]¶
Return the real and imaginary parts of z = A*x, where A = B + iC with
- Parameters:
Ahat – an mxm-dimensional numpy array with Ahat[i,j] = B[i,j] for i>=j and Ahat[i,j] = C[i,j] for i<j.
- Return zr:
m-dimensional numpy arrays containing the real part of z.
- Return zi:
m-dimensional numpy arrays containing the imaginary part of z.
- cla_utils.exercises1.basic_matvec(A, x)[source]¶
Elementary matrix-vector multiplication.
- Parameters:
A – an mxn-dimensional numpy array
x – an n-dimensional numpy array
returns an m-dimensional numpy array which is the product of A with x
This should be implemented using a double loop over the entries of A
- Return b:
m-dimensional numpy array
- cla_utils.exercises1.column_matvec(A, x)[source]¶
Matrix-vector multiplication using the representation of the product Ax as linear combinations of the columns of A, using the entries in x as coefficients.
- Parameters:
A – an mxn-dimensional numpy array
x – an n-dimensional numpy array
- Return b:
an m-dimensional numpy array which is the product of A with x
This should be implemented using a single loop over the entries of x
- cla_utils.exercises1.rank1pert_inv(u, v)[source]¶
Return the inverse of the matrix A = I + uv^*, where I is the mxm dimensional identity matrix, with
- Parameters:
u – m-dimensional numpy array
v – m-dimensional numpy array
- cla_utils.exercises1.rank2(u1, u2, v1, v2)[source]¶
Return the rank2 matrix A = u1*v1^* + u2*v2^*.
- Parameters:
u1 – m-dimensional numpy array
u2 – m-dimensional numpy array
v1 – n-dimensional numpy array
v2 – n-dimensional numpy array
- cla_utils.exercises1.timeable_basic_matvec()[source]¶
Doing a matvec example with the basic_matvec that we can pass to timeit.
cla_utils.exercises10 module¶
- cla_utils.exercises10.GMRES(A, b, maxit, tol, return_residual_norms=False, return_residuals=False)[source]¶
For a matrix A, solve Ax=b using the basic GMRES algorithm.
- Parameters:
A – an mxm numpy array
b – m dimensional numpy array
maxit – integer, the maximum number of iterations
tol – floating point number, the tolerance for termination
return_residual_norms – logical
return_residuals – logical
- Return x:
an m dimensional numpy array, the solution
- Return nits:
if converged, the number of iterations required, otherwise equal to -1
- Return rnorms:
nits dimensional numpy array containing the norms of the residuals at each iteration
- Return r:
mxnits dimensional numpy array, column k contains residual at iteration k
- cla_utils.exercises10.arnoldi(A, b, k)[source]¶
For a matrix A, apply k iterations of the Arnoldi algorithm, using b as the first basis vector.
- Parameters:
A – an mxm numpy array
b – m dimensional numpy array, the starting vector
k – integer, the number of iterations
- Return Q:
an mx(k+1) dimensional numpy array containing the orthonormal basis
- Return H:
a (k+1)xk dimensional numpy array containing the upper Hessenberg matrix
- cla_utils.exercises10.get_AA100()[source]¶
Get the AA100 matrix.
- Return A:
a 100x100 numpy array used in exercises 10.
cla_utils.exercises2 module¶
- cla_utils.exercises2.GS_classical(A)[source]¶
Given an mxn matrix A, compute the QR factorisation by classical Gram-Schmidt algorithm, transforming A to Q in place and returning R.
- Parameters:
A – mxn numpy array
- Return R:
nxn numpy array
- cla_utils.exercises2.GS_modified(A)[source]¶
Given an mxn matrix A, compute the QR factorisation by modified Gram-Schmidt algorithm, transforming A to Q in place and returning R.
- Parameters:
A – mxn numpy array
- Return R:
nxn numpy array
- cla_utils.exercises2.GS_modified_R(A)[source]¶
Implement the modified Gram Schmidt algorithm using the lower triangular formulation with Rs provided from GS_modified_get_R.
- Parameters:
A – mxn numpy array
- Return Q:
mxn numpy array
- Return R:
nxn numpy array
- cla_utils.exercises2.GS_modified_get_R(A, k)[source]¶
Given an mxn matrix A, with columns of A[:, 0:k] assumed orthonormal, return upper triangular nxn matrix R such that Ahat = A*R has the properties that 1) Ahat[:, 0:k] = A[:, 0:k], 2) A[:, k] is normalised and orthogonal to the columns of A[:, 0:k].
- Parameters:
A – mxn numpy array
k – integer indicating the column that R should orthogonalise
- Return R:
nxn numpy array
- cla_utils.exercises2.orthog_cpts(v, Q)[source]¶
Given a vector v and an orthonormal set of vectors q_1,…q_n, compute v = r + u_1q_1 + u_2q_2 + … + u_nq_n for scalar coefficients u_1, u_2, …, u_n and residual vector r
- Parameters:
v – an m-dimensional numpy array
Q – an mxn-dimensional numpy array whose columns are the orthonormal vectors
- Return r:
an m-dimensional numpy array containing the residual
- Return u:
an n-dimensional numpy array containing the coefficients
- cla_utils.exercises2.orthog_proj(Q)[source]¶
Given a vector v and an orthonormal set of vectors q_1,…q_n, compute the orthogonal projector P that projects vectors onto the subspace spanned by those vectors.
- Parameters:
Q – an mxn-dimensional numpy array whose columns are the orthonormal vectors
- Return P:
an mxm-dimensional numpy array containing the projector
- cla_utils.exercises2.orthog_space(V)[source]¶
Given set of vectors u_1,u_2,…, u_n, compute the orthogonal complement to the subspace U spanned by the vectors.
- Parameters:
V – an mxn-dimensional numpy array whose columns are the vectors u_1,u_2,…,u_n.
- Return Q:
an mxl-dimensional numpy array whose columns are an orthonormal basis for the subspace orthogonal to U, for appropriate l.
cla_utils.exercises3 module¶
- cla_utils.exercises3.householder(A)[source]¶
Given a real mxn matrix A, find the reduction to upper triangular matrix R using Householder transformations. The reduction should be done “in-place”, so that A is transformed to R.
- Parameters:
A – an mxn-dimensional numpy array
- cla_utils.exercises3.householder_ls(A, b)[source]¶
Given a real mxn matrix A and an m dimensional vector b, find the least squares solution to Ax = b.
- Parameters:
A – an mxn-dimensional numpy array
b – an m-dimensional numpy array
- Return x:
an n-dimensional numpy array
- cla_utils.exercises3.householder_qr(A)[source]¶
Given a real mxn matrix A, use the Householder transformation to find the full QR factorisation of A.
- Parameters:
A – an mxn-dimensional numpy array
- Return Q:
an mxm-dimensional numpy array
- Return R:
an mxn-dimensional numpy array
- cla_utils.exercises3.householder_solve(A, b)[source]¶
Given a real mxm matrix A, use the Householder transformation to solve Ax_i=b_i, i=1,2,…,k.
- Parameters:
A – an mxm-dimensional numpy array
b – an mxk-dimensional numpy array whose columns are the right-hand side vectors b_1,b_2,…,b_k.
- Return x:
an mxk-dimensional numpy array whose columns are the right-hand side vectors x_1,x_2,…,x_k.
- cla_utils.exercises3.solve_U(U, b)[source]¶
Solve systems Ux_i=b_i for x_i with U upper triangular, i=1,2,…,k
- Parameters:
U – an mxm-dimensional numpy array, assumed upper triangular
b – an mxk-dimensional numpy array, with ith column containing b_i
- Return x:
an mxk-dimensional numpy array, with ith column containing the solution x_i
cla_utils.exercises8 module¶
- cla_utils.exercises8.Q1AQ1s(A)[source]¶
For a matrix A, find the unitary matrix Q1 such that the first column of Q1*A has zeros below the diagonal. Then return A1 = Q1*A*Q1^*.
- Parameters:
A – an mxm numpy array
- Return A1:
an mxm numpy array
- cla_utils.exercises8.ev(A)[source]¶
Given a matrix A, return the eigenvectors of A. This should be done by using your functions to reduce to upper Hessenberg form, before calling hessenberg_ev (which you should not edit!).
- Parameters:
A – an mxm numpy array
- Return V:
an mxm numpy array whose columns are the eigenvectors of A
- cla_utils.exercises8.hessenberg(A)[source]¶
For a matrix A, transform to Hessenberg form H by Householder similarity transformations, in place.
- Parameters:
A – an mxm numpy array
cla_utils.exercises9 module¶
- cla_utils.exercises9.get_A100()[source]¶
Return A100 matrix for investigating QR factoration.
- Return A:
The 100x100 numpy array
- cla_utils.exercises9.get_A3()[source]¶
Return A3 matrix for investigating power iteration.
- Return A3:
a 3x3 numpy array.
- cla_utils.exercises9.get_B100()[source]¶
Return B100 matrix for investigating QR factoration.
- Return A:
The 100x100 numpy array
- cla_utils.exercises9.get_B3()[source]¶
Return B3 matrix for investigating power iteration.
- Return B3:
a 3x3 numpy array.
- cla_utils.exercises9.get_C100()[source]¶
Return C100 matrix for investigating QR factoration.
- Return A:
The 100x100 numpy array
- cla_utils.exercises9.get_D100()[source]¶
Return D100 matrix for investigating QR factoration.
- Return A:
The 100x100 numpy array
- cla_utils.exercises9.inverse_it(A, x0, mu, tol, maxit, store_iterations=False)[source]¶
For a Hermitian matrix A, apply the inverse iteration algorithm with initial guess x0, using the same termination criteria as for pow_it.
- Parameters:
A – an mxm numpy array
mu – a floating point number, the shift parameter
x0 – the starting vector for the power iteration
tol – a positive float, the tolerance
maxit – integer, max number of iterations
store_iterations – if True, then return the entire sequence of inverse iterates, instead of just the final iteration. Default is False.
- Return x:
an m dimensional numpy array containing the final iterate, or if store_iterations, an mxmaxit dimensional numpy array containing all the iterates.
- Return l:
a floating point number containing the final eigenvalue estimate, or if store_iterations, a maxit dimensional numpy array containing all the iterates.
- cla_utils.exercises9.pow_it(A, x0, tol, maxit, store_iterations=False)[source]¶
For a matrix A, apply the power iteration algorithm with initial guess x0, until either
||r|| < tol where
r = Ax - lambda*x,
or the number of iterations exceeds maxit.
- Parameters:
A – an mxm numpy array
x0 – the starting vector for the power iteration
tol – a positive float, the tolerance
maxit – integer, max number of iterations
store_iterations – if True, then return the entire sequence of power iterates, instead of just the final iteration. Default is False.
- Return x:
an m dimensional numpy array containing the final iterate, or if store_iterations, an mxmaxit dimensional numpy array containing all the iterates.
- Return lambda0:
the final eigenvalue.
- cla_utils.exercises9.pure_QR(A, maxit, tol)[source]¶
For matrix A, apply the QR algorithm and return the result.
- Parameters:
A – an mxm numpy array
maxit – the maximum number of iterations
tol – termination tolerance
- Return Ak:
the result
- cla_utils.exercises9.rq_it(A, x0, tol, maxit, store_iterations=False)[source]¶
For a Hermitian matrix A, apply the Rayleigh quotient algorithm with initial guess x0, using the same termination criteria as for pow_it.
- Parameters:
A – an mxm numpy array
x0 – the starting vector for the power iteration
tol – a positive float, the tolerance
maxit – integer, max number of iterations
store_iterations – if True, then return the entire sequence of inverse iterates, instead of just the final iteration. Default is False.
- Return x:
an m dimensional numpy array containing the final iterate, or if store_iterations, an mxmaxit dimensional numpy array containing all the iterates.
- Return l:
a floating point number containing the final eigenvalue estimate, or if store_iterations, an m dimensional numpy array containing all the iterates.