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).

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).

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.