Linear Solver Logs

LinSysSolverLog

Abstract supertype for logging information about a randomized linear system solver.

Note, all descendants that are mutable structs must have fields

• iterations::Int64, which tracks the number of iterations of the solver
• converged::Bool, which tracks whether the solver has converged to the solution (by some notion of convergence that is specified by the user).

LSLogOracle <: LinSysSolverLog

A mutable structure that stores information about a randomized linear solver's behavior. The log assumes that the true solution of the system is known and will be supplied. The goal of this log is usually for research, development, or testing.

Fields

• solution::AbstractVector, a solution to the given linear system.
• collection_rate::Int64, the frequency with which to record information to append to the remaining fields, starting with the initialization (i.e., iteration 0).
• error_hist::Vector{Float64}, retains a vector of numbers corresponding to the error between the iterates of the solver and the solution
• error_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the error size.
• resid_hist::Vector{Float64}, retains a vector of numbers corresponding to the residual (uses the whole system to compute the residual)
• resid_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the residual size.
• iterations::Int64, the number of iterations of the solver.
• converged::Bool, a flag to indicate whether the system has converged by some measure

Constructors

• Calling LSLogOracle(x_star::Vector{Float64}) sets solution = x_star, collection_rate = 1, error_hist = Float64[], error_norm = norm (Euclidean norm), resid_hist = Float64[], resid_norm = norm (Euclidean norm), iterations=-1, and converged = false.
• Calling LSLogOracle(x_star::Vector{Float64}, cr::Int64) sets the structure with the same parameters as for LSLogOracle(x_star) except collection_rate = cr.

LSLogFull <: LinSysSolverLog

A mutable structure that stores information about a randomized linear solver's behavior. The log assumes that the full linear system is available for processing. The goal of this log is usually for research, development or testing as it is unlikely that the entire residual vector is readily available.

Fields

• collection_rate::Int64, the frequency with which to record information to append to the remaining fields, starting with the initialization (i.e., iteration 0).
• resid_hist::Vector{Float64}, retains a vector of numbers corresponding to the residual (uses the whole system to compute the residual)
• resid_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the residual size.
• iterations::Int64, the number of iterations of the solver.
• converged::Bool, a flag to indicate whether the system has converged by some measure

Constructors

• Calling LSLogFull() sets collection_rate = 1, resid_hist = Float64[], resid_norm = norm (Euclidean norm), iterations = -1, and converged = false.
• Calling LSLogFull(cr::Int64) is the same as calling LSLogFull() except collection_rate = cr.

LSLogMA <: LinSysSolverLog

A mutable structure that stores information about a randomized linear solver's behavior. The log assumes that only a random block of full linear system is available for processing. The goal of this log is usually for all use cases as it acts as a cheap approximation of the full residual.

Fields

• collection_rate::Int64, the frequency with which to record information to append to the remaining fields, starting with the initialization (i.e., iteration 0).
• ma_info::MAInfo, structure that holds information relevant only to moving average, like the two choices of moving average widths (lambda1 and lambda2), the current moving average width (lambda), a flag to indicate which moving average regime, between lambda1 and lambda2, is being used, a vector containing the values to be averaged (res_window), and an indicator of where the next value should be placed (idx).
• resid_hist::Vector{Float64}, a structure that contains the moving average of the error proxy, typically the norm of residual or gradient of normal equations.
• iota_hist::Vector{Float64}, a structure that contains the moving average of the error proxy, typically the norm of residual or gradient of normal equations.
• width_hist::Vector{Int64}, data structure that contains the widths used in the moving average calculation at each iteration.
• resid_norm::Function, a function that accepts a single vector argument and returns a scalar. Used to compute the residual size.
• iterations::Int64, the number of iterations of the solver.
• converged::Bool, a flag to indicate whether the system has converged by some measure.
• true_res, a boolean indicating if we want the true residual computed instead of approximate.
• dist_info::DistInfo, a structure that stores information about the sub-Exponential distribution.

Constructors

• Calling LSLogMA() sets collection_rate = 1, lambda1 = 1, lambda2 = 30, resid_hist = Float64[], iota_hist = Float64[], width_hist = Int64[], resid_norm = norm (Euclidean norm), iterations = -1, converged = false, sampler = LinSysVecRowDetermCyclic, max_dimension = 0, sigma2 = nothing, omega = nothing, eta = 1, and true_res = false. The user can specify their own values of lambda1, lambda2, sigma2, omega, and eta using key word arguments as inputs into the constructor.

log_update!(
    log::LinSysSolverLog,
    sampler::LinSysSampler,
    x::AbstractVector,
    samp:s:Tuple,
    iter::Int64,
    A,
    b)

A common interface for specifying different strategies for updating the log with supertype LinSysSolverLog. A sampler of supertype LinSysSampler can be used to provide specific multiple implementations for the same log type. x is the iterate value. samp is the output generated by the sample function (see linears_samplers.jl). iter is the current iteration counter. A and b specify the linear system.

get_uncertainty(log::LSLogMA; alpha = .95)

A function that takes a LSLogMA type and a confidence level, alpha, and returns credible intervals for for every rho in the log, specifically it returns a tuple with (rho, Upper bound, Lower bound).

MAInfo

A mutable structure that stores information relevant to the moving average of the progress estimator.

Fields

• lambda1::Int64, the width of the moving average during the fast convergence phase of the algorithm, this has a default value of one.
• lambda2::Int64, the width of the moving average in the slower convergence phase, this has a default value of 30.
• lambda::Int64, the value of the moving average width at the current iteration.
• flag::Bool, A boolean indicating which phase we are in, a value of true indicates second phase.
• idx::Int64, The index indcating what value should be replaced in the moving average buffer.
• res_window::Vector{Float64} - The moving average buffer.

DistInfo

A mutable structure that stores information about the sub-Exponential distribution.

Fields

• sampler::Union{DataType, Nothing}, The type of sampler being used.
• max_dimension::Int64, The dimension that is being sampled.
• block_dimension::Int64, The sampling dimension.
• sigma2::Union{Float64, Nothing}, The variance parameter in the sub-Exponential distribution, if not given is determined for sampling method.
• omega::Union{Float64, Nothing}, The exponential distrbution parameter, if not given is determined for sampling methods.
• eta::Float64, A parameter for adjusting the conservativeness of the distribution, higher value means a less conservative estimate. By default, this is set to one.

update_ma!(
    log::LSLogMA, 
    res::Union{AbstractVector, Real}, 
    lambda_base::Int64, 
    iter::Int64
)

Function that updates the moving average tracking statistic. This function is not exported and thus the user has no direct access.

Inputs

• log::LSLogMA, the moving average log structure.
• `res::Union{AbstractVector, Real}, the residual for the current iteration. This could be sketeched or full residual depending on the inputs when creating the log structor.

-lambda_base::Int64, which lambda, between lambda1 and lambda2, is currently being used. -iter::Int64, the current iteration.

Outputs

Performs and inplace update of the log datatype.

get_SE_constants!(log::LSLogMA, sampler::Type{T<:LinSysSampler})

A function that returns a default set of sub-Exponential constants for each sampling method. This function is not exported and thus the user does not have direct access to it.

Inputs

• log::LSLogMA, the log containing al the tracking information.
• sampler::Type{LinSysSampler}, the type of sampler being used.

Outputs

Performs an inplace update of the sub-Exponential constants for the log.