Linear Subsolvers

LinSysSolveRoutine

Abstract supertype that specifies the type of linear system solver routine being deployed.

LinSysVecRowProjection <: LinSysSolveRoutine

Abstract supertype for vector row action projection methods.

LinSysVecColProjection <: LinSysSolveRoutine

Abstract supertype for vector column action projection methods.

LinSysBlkRowProjection <: LinSysSolveRoutine

Abstract supertype for block row action projection methods.

LinSysBlkColProjection <: LinSysSolveRoutine

Abstract supertype for block column action projection methods.

LinSysPreconKrylov <: LinSysSolveRoutine

Abstract supertype for preconditioned Krylov solver.

LinSysVecRowProjStd <: LinSysVecRowProjection

A mutable structure that represents a standard row projection method.

Aliases

• Kaczmarz, see Kaczmarz, M. S. "Approximate solution of systems of linear equations." (1937). Original article is in German.
• ART, see Gordon, Richard, Robert Bender, and Gabor T. Herman. "Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography." Journal of theoretical Biology 29.3 (1970): 471-481.

Fields

• alpha::Float64, a relaxation parameter that should be set between 0.0 and 2.0

Calling LinSysVecRowProjStd() defaults the relaxation parameter to 1.0.

LinSysVecRowProjPO <: LinSysVecRowProjection

A mutable structure that represents the standard row projection method with orthogonalization of the current projection against a set of m previous projection directions, where m is specified by the user.

See Patel, Vivak, Mohammad Jahangoshahi, and Daniel Adrian Maldonado. "An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems." SIAM Journal on Matrix Analysis and Applications (2021) 42:2, 800-831. https://doi.org/10.1137/19M1259481

Fields

• α::Float64, the relaxation parameter (usually between 0.0 and 2.0)
• m::Int64, the number of previous directions against which to orthogonalize
• Z::Union{Vector{Vector{Float64}}, Nothing}, stores the m vectors against which the current projection is orthogonalized against

Calling LinSysVecRowProjPO() defaults the relaxation parameter to 1.0, the memory parameter m to 5, and Z to nothing.

LinSysVecRowProjFO <: LinSysVecRowProjection

A mutable structure that represents the standard row projection method with full orthogonalization against all previous projections. Equivalently, this type represents a solver for incrementally constructed matrix sketches.

See McCormick, S. F. "The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space." Indiana University Mathematics Journal 26.6 (1977): 1137-1150. https://www.jstor.org/stable/24891603

See Patel, Vivak, Mohammad Jahangoshahi, and Daniel Adrian Maldonado. "An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems." SIAM Journal on Matrix Analysis and Applications (2021) 42:2, 800-831. https://doi.org/10.1137/19M1259481

Fields

• S::Union{Matrix{Float64}, Nothing} is a matrix used for orthogonalizing against all previous search directions.

Calling LinSysVecRowProjFO() defaults to LinSysVecRowProjFO(nothing).

IterativeHessianSketch <: LinSysSolveRoutine

A mutable structure that represents the Iterative Hessian Sketch Method.

See Mert Pilanci and Martin J. Wainwright. "Iterative Hessian Sketch: Fast and Accurate Solution Approximation for Constrained Least-Squares." Journal of Machine Learning Research, 17(53), 1–38. http://jmlr.org/papers/v17/14-460.html

Fields

• A::AbstractArray, the coefficient matrix for the linear system. Required as we need to compute the full residual.
• b::AbstractVector, the constant term (i.e., the linear system is Ax = b). Required as we need to compute the full residual.
• step::Union{AbstractVector, Nothing}, buffer array to hold solution of subproblem that provides update to x.
• btilde::Union{AbstractVector, Nothing}, buffer array to hold constant term in forming the subproblem to compute step.

Constructors

    IterativeHessianSketch(A, b)

Arguments

• A::AbstractArray, the coefficient matrix for the linear system. Required as we need to compute the full residual.
• b::AbstractVector, the constant term (i.e., the linear system is Ax = b). Required as we need to compute the full residual.

LinSysVecColProjStd <: LinSysVecColProjection

A mutable structure that represents a standard column projection method.

See Luo, Zhi-Quan, and Paul Tseng. "On the convergence of the coordinate descent method for convex differentiable minimization." Journal of Optimization Theory and Applications 72.1 (1992): 7-35.

For a generalization, see Patel, Vivak, Mohammad Jahangoshahi, and Daniel Adrian Maldonado. "An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems." SIAM Journal on Matrix Analysis and Applications (2021) 42:2, 800-831. https://doi.org/10.1137/19M1259481

Aliases

• CoordinateDescent
• GaussSeidel

Fields

• alpha::Float64, a relaxation parameter that should be set between 0.0 and 2.0

Calling LinSysVecColProjStd() defaults the relaxatoin parameter to 1.0.

LinSysVecColProjPO <: LinSysVecColProjection

A mutable structure that represents the standard column projection method with orthogonalization of the current projection against a set of m previous projection directions, where m is specified by the user.

See Patel, Vivak, Mohammad Jahangoshahi, and Daniel Adrian Maldonado. "An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems." SIAM Journal on Matrix Analysis and Applications (2021) 42:2, 800-831. https://doi.org/10.1137/19M1259481

Fields

• α::Float64, the relaxation parameter (usually between 0.0 and 2.0)
• m::Int64, the number of previous directions against which to orthogonalize
• Z::Union{Vector{Vector{Float64}}, Nothing}, stores the m vectors against which the current projection is orthogonalized against

Calling LinSysVecColProjPO() defaults the relaxation parameter to 1.0, the memory parameter m to 5, and Z to nothing.

LinSysVecColProjFO <: LinSysVecColProjection

A mutable structure that represents the standard column projection method with full orthogonalization against all previous projections.

See Patel, Vivak, Mohammad Jahangoshahi, and Daniel Adrian Maldonado. "An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems." SIAM Journal on Matrix Analysis and Applications (2021) 42:2, 800-831. https://doi.org/10.1137/19M1259481

Fields

• S::Union{Matrix{Float64}, Nothing} is a matrix used for orthogonalizing against all previous search directions.

Calling LinSysVecColProjFO() defaults to LinSysVecColProjFO(nothing).

LinSysBlkRowLQ <: LinSysBlkRowProjection

A mutable structure that represents a standard block row projection method.

Aliases

• BlockKaczmarz

Fields

• α::Float64, a relaxation parameter that should be set between 0.0 and 2.0
• update::Union{Nothing, AbstractArray}, a buffer for storing update.

Constructors

Calling LinSysBlkRowProj() defaults the relaxation parameter to 1.0.

LinSysBlkColGent <: LinSysBlkColProjection

A mutable structure that represents a standard block column projection method that projects a previous iterate onto the columnspace of an inputted block. This method can be viewed as a generalization to block coordinate descent. The updates to this are computed using Gentleman's Algorithm.

For more information on Gentleman's see: 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.

Aliases

• BlockCoordinateDescent

Fields

• α::Float64, a relaxation parameter that should be set between 0.0 and 2.0
• gent::GentData, a buffer to store important information related to the Gentleman's

incremental QR least squares solver.

• update::Union{Nothing, AbstractArray}, a buffer for storing update.
• rowsize::Int64, the upper limit on the size of the row blocks in Gentleman's. By default this is set to 10000.

Constructors

Calling the constructor LinSysBlkColProj() defaults the relaxation parameter to 1.0.

rsubsolve!(
    type::LinSysSolveRoutine,
    x::AbstractVector,
    samp::Tuple,
    iter::Int64)

A common interface for specifying different strategies for solving a subproblem generated by a sampling, selecting or sketching operation on a linear system. The type argument is used to select the appropriately defined strategy. The argument x is the current iterate value for the solution. The argument samp depends on the subtype of LinSysSolveRoutine that is being deployed and is described below. The iter argument is the iteration counter.

The value of samp depends on the type of subtype of LinSysSolveRoutine being deployed. To describe this, let A be the coefficient matrix of the system, and b its constant vector.

• For T<:LinSysVecRowProjection, samp is a two-dimensional tuple where the first entry is a vector in the row space of A; and the second entry is a scalar value corresponding to a linear combination of the elements of b.
• For T<:LinSysVecColProjection, samp is a three-dimensional tuple where the first entry is a vector of length(x) corresponding to the search direction; the second entry is a matrix with the same number of rows as A (usually it is A); and the third entry is a scalar-valued residual for the normal system corresponding to samp[1]'* A' * (A * x - b).

The function rsubsolve! updates the quantity x and any fields of type that must be updated.