Linear Samplers

LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting components of a linear system.

Aliases

• LinSysSketch
• LinSysSelect

LinSysVecRowSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a row space element from a linear system.

Aliases

• LinSysVecRowSketch
• LinSysVecRowSelect

LinSysVecColSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a column space element from a linear system.

Aliases

• LinSysVecColSketch
• LinSysVecColSelect

LinSysBlkRowSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a collection of row space elements from a linear system.

Aliases

• LinSysBlkRowSketch
• LinSysBlkRowSelect

LinSysBlkColSampler <: LinSysSampler

Abstract supertype for sampling, sketching or deterministically selecting a collection of column space elements from a linear system.

Aliases

• LinSysBlkColSketch
• LinSysBlkColSelect

LinSysVecRowDetermCyclic <: LinSysVecRowSelect

An immutable structure without any fields. Specifies deterministic cycling through the equations of a linear system.

LinSysVecRowHopRandCyclic <: LinSysVecRowSelect

A mutable structure that specifies a cycling through the rows of a linear system, where the cycling order is determined randomly once the current cycling order has been used hop number of times. The solver randomly chooses the cycling order whenever necessary.

Fields

• order::Union{Vector{Int64},Nothing}
• hop::Int64

Constructors

• LinSysVecRowHopRandCyclic() defaults to setting the order to nothing and the hop to 5 (i.e., each ordering is used five times before sampling a new ordering).
• LinSysVecRowHopRandCyclic(hop::Int64) defaults to setting the order to nothing and the hop to whatever is specified by the argument.

LinSysVecRowOneRandCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. Randomly specifies a cycling order over the equations of a linear system. Once this ordering is specified, the ordering is kept fixed.

Fields

• order::Union{Vector{Int64},Nothing}

Calling LinSysVecRowOneRandCyclic() defaults to setting order to nothing. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecRowPropToNormSampler{T} <: LinSysVecRowSampler where T <: Categorical

A parametric mutable structure that specifies sampling from the rows of the equation where the probability of selecting a given equation is proportional to the sum of squares of the coefficients of the given equation. The solver will appropriately initialize the distribution.

See Strohmer, T., Vershynin, R. A Randomized Kaczmarz Algorithm with Exponential Convergence. J Fourier Anal Appl 15, 262 (2009). https://doi.org/10.1007/s00041-008-9030-4

Aliases

• LinSysVecRowSVSampler

Fields

• dist::T, a categorical probability distribution.

Calling LinSysVecRowPropToNormSampler() or LinSysVecRowSVSampler() defaults dist to Categorical(1.0).

LinSysVecRowRandCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. Randomly specifies a cycling order the equations of a linear system. Once this ordering is exhausted by the solver, a new random ordering is specified. This process is repeated

Fields

• order::Union{Vector{Int64},Nothing}

Calling LinSysVecRowOneRandCyclic() defaults to setting order to nothing. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecRowUnidSampler <: LinSysVecRowSampler

An immutable structure without fields that specifies randomly cycling from the rows of a linear system with uniform probability and with replacement.

LinSysVecRowUnifSampler <: LinSysVecRowSampler

An immutable structure without fields that specifies taking a linear combination of all equations with the coefficients being independent uniform random variables.

LinSysVecRowSparseUnifSampler <: LinSysVecRowSelect

A mutable structure that specifies sampling a proporition of the rows of a linear system, scaling each using independent uniform random variables, and then taking their sum. The proportion of rows sampled without replacement is given by (at most) sparsity which must be between 0 and 1 (not inclusive).

Fields

• sparsity::Float64

Constructors

• LinSysVecRowSparseUnifSampler() defaults the sparsity level to 0.2.

LinSysVecRowGaussSampler <: LinSysVecRowSampler

An immutable structure without fields that specifies taking a linear combination of all equations with the coefficients being independent Gaussian random variables.

LinSysVecRowSparseGaussSampler <: LinSysVecRowSelect

A mutable structure that specifies sampling a proporition of the rows of a linear system, scaling each using independent Gaussian random variables, and then taking their sum. The proportion of rows sampled without replacement is given by (at most) sparsity which must be between 0 and 1 (not inclusive).

Fields

• sparsity::Float64

Constructors

• LinSysVecRowSparseUnifSampler() defaults the sparsity level to 0.2.

LinSysVecRowMaxResidual <: LinSysVecRowSelect

An immutable structure without fields that specifies choosing the linear equation in a system with the largest absolute residual at the current iterate.

LinSysVecRowResidCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. When the ordering is not specified, the ordering is filled by looking at the residuals at the current iterate and ordering by decreasing residual. Once the order is exhausted a new order is selected.

Fields

• order::Vector{Int64}

Calling LinSysVecRowResidCyclic() defaults to setting order to an empty array. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecRowMaxDistance <: LinSysVecRowSelect

An immutable structure without fields that specifies choosing the linear equation in a system with the largest distance between the current iterate and the hyperplane specified by the equation.

LinSysVecRowDistCyclic <: LinSysVecRowSelect

A mutable structure with a field to store a cycling order. When the ordering is not specified, the ordering is filled in two steps. First, the distances between the current iterate and all hyperplanes as specified by the equations of the system. Then, the ordering is the indices of these distances in decreasing order.

Fields

• order::Vector{Int64}

Calling LinSysVecRowDistCyclic() defaults to setting order to an empty array. The sample function will handle the re-initialization of the fields once the system is provided.

LinSysVecColDetermCyclic <: LinSysVecColSelect

An immutable structure without any fields. Specifies deterministic cycling through the columns of a linear system.

LinSysVecColOneRandCyclic <: LinSysVecColSelect

A mutable structure with a field to store a cycling order. Randomly specifies a cycling order over the equations of a linear system. Once this ordering is specified, the ordering is kept fixed.

Fields

• order::Vector{Int64}

Calling LinSysVecColOneRandCyclic() defaults to setting order to nothing. The sample function will handle the re-initialization of the fields once the system is provided.

sample(type::T where T<:LinSysSampler,
    A::AbstractArray,
    b::AbstractVector,
    x::AbstractVector,
    iter::Int64)

A common interface for specifying different strategies for sampling, selecting or sketching a linear system specified by A and b. The type argument is used to select the an appropriately defined strategy. The argument x is the current iterate value for the solution. The arguent iter is the iteration counter.

The value(s) returned by sample depend on the subtype of LinSysSampler being used. Specifically,

• For T<:LinSysVecRowSampler, a vector in the row space of A and constant are returned
• For T<:LinSysVecColSampler, a vector of length(x), the matrix A, and a scalar-valued residual are returned.