Linear Solver Helpers

GentData{S, M<:Matrix{S}, V<:Vector{S}}

This is a preallocated data structure for solving least squares problems with Gentleman's algorithm. This data structure is not exported and thus is not designed to be manipulated by the user.

Fields

• A::M, the matrix to be solved.
• B::M, the block of rows of A that are used to update the QR decomposition.
• R::UpperTriangular, the upper triangular part of B.
• tab::SubArray, the last column of B where the constant vector entries corresponding

to the rows of A that were brought to B are stored.

• v::V, a buffer vector that stores the scaling constants from the Householder reflections,

see LAPACK.geqrf! in LinearAlgebra for more information.

• bsize::Int64, the number of rows transported to B at each iteration.

Calling Gent(A, bsize) will allocate a B matrix with the n + 1 columns and n + bsize + 1 rows where n is the number of columns of A. It also allocates a buffer vector v with n + 1 entries. Finally, it allocates a view of the upper triangular part of B[1:n, 1:n] and a view of the last column of B.

Miller, Alan J. “Algorithm AS 274: Least Squares Routines to Supplement Those of Gentleman.” Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 41, no. 2, 1992, pp. 458–78. JSTOR, https://doi.org/10.2307/2347583.

gentleman!(G::GentData)

A function that updates the GenData structure with the Gentleman's algorithm applied to a single row block of A.

Inputs

• G::GentData, a data structure with the information to be updated

by an iteration of Gentlemans.

Output

The function will result in updates to the upper triangular part R and the tab vector of the GentData structure.

ldiv!(x::AbstractVector, G::GentData, b::AbstractVector)

Function that takes the allocated GentData structure to solve the least squares problem $\min_x \|A x-b\|_2^2$. The function overwrites x with the solution.

copyBlockFromMat!(B::AbstractMatrix, A::AbstractMatrix, b::AbstractVector, index::Union{UnitRange{Int64}, Vector{Int64}})

Function that updates matrix B with the entries at indicies index corresponding to the rows of the A matrix and the entries of the b constant vector of the linear system.

resetGent!(G::GentData)

Function that sets all the allocated memory of GentData to zero.

mgs!(q::AbstractVector, basis::AbstractMatrix)

Perform the modified Gram-Schmidt to orthogonalize q with respect to the set of vectors in basis.

Arguments

• q::AbstractVector, vector that will be orthogonalized.
• basis::AbstractMatrix, basis to orthogonalize against.

Returns

• h::AbstractVector, orthogonalizing coefficients.

mgs!(q::AbstractVector, h::AbstractVector, basis::AbstractMatrix)

Perform the modified Gram-Schmidt to orthogonalize q against the vectors in basis.

Arguments

• q::AbstractVector, vector that will be orthogonalized.
• h::AbstractVector, view of a matrix to store the orthogonalizing coefficients
• basis::AbstractMatrix, basis to orthogonalize against.

arnoldi(A::AbstractMatrix, q::AbstractVector, k::Int64)

Method

Compute a orthonormal basis for the Krylov subspace

\[\text{span}(q, Aq, ..., A^{k-1}q),\]

and returns the basis vectors and an upper Hessenberg matrix that contains the coefficients for orthogonalization. The hessenberg matrix, $H$, and basis matrix, $Q$, satisfy

\[A Q_{k-1} = Q H,\]

and

\[Q_{k-1}^\intercal A Q_{k-1} = H_{k-1}.\]

where $Q_{k-1}$ contains the first $k-1$ columns of the matrix $Q$, and $H_{k-1}$ contains the first $k-1$ rows of the matrix $H$.

Reference(s)

Timsit, Grigori, Balabanov. "Randomized Orthogonal Projection Methods for Krylov Subspace Solvers". arxiv, https://arxiv.org/pdf/2302.07466

Lloyd N. Trefethen and David Bau III. "Numerical Linear Algebra". SIAM, 1997, Lecture 33.

Arguments

• A::AbstractMatrix, matrix used for the krylov subspace
• q::AbstractVector, vector used for the krylov subspace
• k::Int64, order of the krylov subspace. Number of vectors in krylov subspace.

Returns

• Q::Matrix{Float64}, orthogonal basis vector for the krylov subspace. Is of dimension

(size(q,1), k).

• H::Matrix{Float64}, upper hessenberg matrix containing orthogonalizing coefficients. Is

of dimension (k, k - 1).

randomized_arnoldi(A::AbstractMatrix, q::AbstractVector, Omega::AbstractMatrix,
    k::Int64)

Method

Computes a sketched orthonormal basis for the Krylov subspace

\[\text{span}(q, Aq, ..., A^{k-1}q),\]

and returns basis vectors that are approximately orthogonal, the sketched basis vectors, and an upper Hessenberg matrix containing the orthogonalizing coefficients for the sketched basis.

Let $Q$, $S$, and $H$ be the matrices defined above, and let $\Omega$ be the sketching matrix. A sketched orthonormal basis formed by the columns of $S$ is a orthonormal basis for the vector space defined by

\text{span}(\Omega q, \Omega A q, \Omega A^{k-1} q).

Furthermore, these matrix follow the following relationships.

\[A Q_{k-1} = Q H,\]

and

\[(\Omega Q_{k-1})^{\intercal} \Omega A Q_{k-1} = H_{k-1},\]

where $Q_{k-1}$ contains the first $k-1$ columns of the matrix $Q$, and $H_{k-1}$ is the first $k-1$ rows of the matrix $H$.

Reference(s)

Timsit, Grigori, Balabanov. "Randomized Orthogonal Projection Methods for Krylov Subspace Solvers". arxiv, https://arxiv.org/pdf/2302.07466

Arguments

• A::AbstractMatrix, matrix that is used to form Krylov subspace.
• q::AbstractVector, vector used to form krylov subspace.
• Omega::AbstractMatrix, sketching matrix.
• k::Int64, how many vectors to add to basis.

Returns

• Q::AbstractMatrix, approximate basis vectors. Is of dimension (size(q, 1), k).
• S::AbstractMatrix, sketched basis vectors. Is of dimension (size(Omega, 1), k).
• H::AbstractMatrix, upper hessenberg matrix that stores the orthogonalizing

coefficients for the sketched basis vectors. Is of dimension (k, k - 1).