Solvers

Solver

An abstract supertype for structures that contain the user-controlled parameters for methods that solve linear systems and least squares problems.

SolverRecipe

An abstract supertype specifying a solver method with pre-allocated data structures given a coefficient matrix and constant vector.

Kaczmarz <: Solver

An implementation of a Kaczmarz solver. Specifically, it is a solver that iteratively updates an iterate by projecting the iterate onto (a subspace of) the row space of a consistent linear system.

Mathematical Description

Let $A$ be an $m \times n$ matrix and consider the consistent linear system $Ax=b$. We can view the solution to this linear system as lying at the intersection of the row hyperplanes, $\cap_{i \in \{1, \ldots, m\}}\{u \in \mathbb{R}^{n} : A_{i \cdot} u = b_i \}$, where $A_{i \cdot}$ represents the $i^\text{th}$ row of $A$. One way to find this interesection is to iteratively project some abritrary point, $x$ from one hyperplane to the next, through $x_{+} = x + \alpha \frac{b_i - \lange A_{i\cdot}, x\rangle}{\| A_{i\cdot}.$ Doing this with random permutation of $i$ can lead to a geometric convergence [6]. Here $\alpha$ is viewed as an over-relaxation parameter and can improve convergence. One can also generalize this procedure to blocks by considering the $S$ being a $s \times n$ random matrix. If we let $\tilde A = S A$ and $\tilde b = Sb$ then we can perform block kaczmarz as described by [7] with $x_{+} = x + \alpha \tilde A^\top (\tilde A \tilde A^\top)^\dagger (\tilde b - \tilde A x).$ While, S is often random, in reality, whether S is deterministic or random is quite flexible see [8] for more details.

Fields

• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence.
• compressor::Compressor, a technique for forming the compressed rowspace of the linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.
• sub_solver::SubSolver, a technique to perform the projection of the solution onto the compressed rowspace.

Constructor

Kaczmarz(;
    compressor::Compressor = SparseSign(), 
    log::Logger = BasicLogger(),
    error::SolverError = FullResidual(),
    sub_solver::SubSolver = LQSolver(),
    alpha::Float64 = 1.0
)

Keywords

• compressor::Compressor, a technique for forming the compressed rowspace of the linear system.
• log::Logger, a technique for logging the progress of the solver.
• error::SolverError, a method for estimating the progress of the solver.
• sub_solver::SubSolver, a technique to perform the projection of the solution onto the compressed rowspace. When the compression_dim = 1 this is not used.
• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence. By default this value is 1.

Returns

• A Kaczmarz object.

KaczmarzRecipe{
    T<:Number, 
    V<:AbstractVector,
    M<:AbstractMatrix, 
    VV<:SubArray,
    MV<:SubArray,
    C<:CompressorRecipe, 
    L<:LoggerRecipe,
    E<:SolverErrorRecipe, 
    B<:SubSolverRecipe
} <: SolverRecipe

A mutable structure containing all information relevant to the Kaczmarz solver. It is formed by calling the function complete_solver on Kaczmarz solver, which includes all the user controlled parameters, and the linear system matrix A and constant vector b.

Fields

• compressor::CompressorRecipe, a technique for forming the compressed rowspace of the linear system.
• log::LoggerRecipe, a technique for logging the progress of the solver.
• error::SolverErrorRecipe, a method for estimating the progress of the solver.
• sub_solver::SubSolverRecipe, a technique to perform the projection of the solution onto the compressed rowspace.
• alpha::Float64, the over-relaxation parameter. It is multiplied by the update and can affect convergence.
• compressed_mat::AbstractMatrix, a matrix container for storing the compressed matrix. Will be set to be the largest possible block size.
• compressed_vec::AbstractVector, a vector container for storing the compressed constant vector. Will be set to be the largest possible block size.
• solution_vec::AbstractVector, a vector container for storing the solution to the linear system.
• update_vec::AbstractVector, a vector container for storing the update to the linear system.
• mat_view::SubArray, a container for storing a view of compressed matrix container. Using views here allows for variable block sizes.
• vec_view::SubArray, a container for storing a view of the compressed vector container. Using views here allows for variable block sizes.

complete_solver(solver::Solver, x::AbstractVector, A::AbstractMatrix, b::AbstractVector)

A function that generates a SolverRecipe given the arguments.

Arguments

• solver::Solver, a user-specified solver method.
• x::AbstractVector, a vector for the proposed solution.
• A::AbstractMatrix, a coefficient matrix.
• b::AbstractVector, a constant vector.

Outputs

• A SolverRecipe object.

rsolve!(
    solver::SolverRecipe, 
    x::AbstractVector, 
    A::AbstractMatrix, 
    b::AbstractVector
)

A function that solves a linear system given the arguments.

Arguments

• solver::SolverRecipe, a fully initialized realization for a solver method for a specific linear system.
• x::AbstractVector, a vector for the proposed solution.
• A::AbstractMatrix, a coefficient matrix.
• b::AbstractVector, a constant vector.

Outputs

• Returns nothing. Updates the SolverRecipe and x in place.

rsolve!(
    solver::Solver, 
    x::AbstractVector, 
    A::AbstractMatrix, 
    b::AbstractVector
)

A function that solves a linear system given the arguments.

Arguments

• solver::Solver, a user-specified solver method.
• x::AbstractVector, a vector for the proposed solution.
• A::AbstractMatrix, a coefficient matrix.
• b::AbstractVector, a constant vector.

Outputs

• x::AbstractVector, a proposed solution to a linear system or least squares problem.
• A SolverRecipe object.

kaczmarz_update!(solver::KaczmarzRecipe)

A function that performs the Kaczmarz update when the compression dimension is one. If $a$ is the resulting compression of the coefficient matrix, and $c$ is the resulting compression of the constant vector, then we perform the update: $x = x - \alpha (a^\top x -c) / \|a\|_2^2$.

Arguments

• solver::KaczmarzRecipe, the solver information required for performing the update.

Outputs

• returns nothing

kaczmarz_update_block!(solver::KaczmarzRecipe)

A function that performs the kaczmarz update when the compression dim is greater than 1. In the block case where the compressed matrix $\tilde A$, and the compressed contant vector $\tilde b$, we perform the updated: $x = x - \alpha \tilde A^\top (\tilde A \tilde A^\top)^\dagger (\tilde Ax-\tilde b)$.

Arguments

• solver::KaczmarzRecipe, the solver information required for performing the update.

Outputs

• returns nothing

dotu(a::AbstractArray, b::AbstractArray)

A function that computes the non conjugate dot product between two vectors. It is equivalent to calling dot(conj(a), b).

Arguments

• a::AbstractArray, a vector being dot producted (is labeled as a array to allow for views).
• b::AbstractArray, a vector being dot producted (is labeled as a array to allow for views).

Returns

• A scalar that is the non-conjugated dot product between two vectors.