maxvol_generic!(A, tol=1.05, maxiters=100)

Generic maxvol method, that does not use any BLAS or LAPACK calls.

Finds good square submatrix. Uses greedy iterative maximization of 1-volume to find good r-by-r submatrix in a given N-by-r matrix A of rank r. Returns good submatrix and coefficients of expansion (N-by-r matrix) of rows of matrix A by rows of good submatrix.

Can be used for special arithmetics, like BigFloat, Rational or Complex{Float16}.

Arguments:

• A::Matrix: Input matrix on entry and output coefficients on exit.
• tol::Float64: Stop when determinant growth is less or equal to this.
• maxiters::Int: Maximum number of iterations.

Returns:

• piv::Vector{Int}: Indexes of pivoted rows
• niters::Int: Number of performed swap iterations

Example:

julia> using Random, LinearAlgebra, Maxvol
julia> rng = MersenneTwister(100);
julia> A = rand(rng, BigFloat, 1000, 100);
julia> C = copy(A);
julia> piv, niters = maxvol_generic!(C);
julia> norm(A-C*A[piv,:]) / norm(A)
2.030657951400512330834848952202721164346464876711701213634530270353170311161736e-76
julia> A = rand(rng, ComplexF64, 1000, 100);
julia> C = copy(A);
julia> piv, niters = maxvol_generic!(C);
julia> norm(A-C*A[piv,:]) / norm(A)
4.863490630095799e-15

See also: maxvol!

maxvol!(A, tol=1.05, maxiters=100)

Finds good square submatrix. Uses greedy iterative maximization of 1-volume to find good r-by-r submatrix in a given N-by-r matrix A of rank r. Returns good submatrix and coefficients of expansion (N-by-r matrix) of rows of matrix A by rows of good submatrix.

Uses vendor-optimized LAPACK, provided by Julia. Supports only 4 input types: Float32 (single), Float64 (double), ComplexF32 (single complex) and ComplexF64 (double complex).

Arguments:

• A::Matrix{T}: Input matrix on entry and output coefficients on exit. T must be one of Float32, Float64, ComplexF32 and ComplexF64.
• tol::Float64: Stop when determinant growth is less or equal to this.
• maxiters::Int: Maximum number of iterations.

Returns:

• piv::Vector{Int}: Indexes of pivoted rows
• niters::Int: Number of performed swap iterations

Example:

julia> using Random, LinearAlgebra, Maxvol
julia> rng = MersenneTwister(100);
julia> A = rand(rng, Float64, 1000, 100);
julia> C = copy(A);
julia> piv, niters = maxvol!(C);
julia> norm(A-C*A[piv,:]) / norm(A)
2.3975097489579994e-15
julia> A = rand(rng, ComplexF32, 1000, 100);
julia> C = copy(A);
julia> piv, niters = maxvol!(C);
julia> norm(A-C*A[piv,:]) / norm(A)
2.0852597f-6

See also: maxvol_generic!

rect_maxvol_generic(A, tol=1.0, maxK=size(A,1), min_add_K=0,
    min_K=size(A,2), start_maxvol_iters=10, identity_submatrix=true)

Generic rect_maxvol method, that does not call BLAS or LAPACK directly.

Finds good rectangular submatrix. Uses greedy iterative maximization of 2-volume to find good K-by-r submatrix in a given N-by-r matrix A of rank r. Returns good submatrix and least squares coefficients of expansion (N-by-K matrix) of rows of matrix A by rows of good submatrix.

Can be used for special arithmetics, like BigFloat, Rational or Complex{Float16}.

Arguments:

• A::Matrix: Input matrix on entry.
• tol::Float64: Stop when volume growth is less or equal to this.
• maxK::Int: Maximum number of rows in good submatrix.
• minK::Int: Minimum number of rows in good submatrix.
• min_add_K::Int: Minimum number of rows to add to the square submatrix. Resulting good matrix will have minimum of r+min_add_K rows.
• start_maxvol_iters::Int: How many iterations of square maxvol (optimization of 1-volume) is required to be done before actual rectangular 2-volume maximization.
• identity_submatrix::Bool: Coefficients of expansions are computed as least squares solution. If identity_submatrix is True, returned matrix of coefficients will have submatrix, corresponding to good rows, set to identity.

Returns:

• piv::Vector{Int}: Indexes of pivoted rows
• C::Matrix: N-by-size(piv) matrix of coefficients of expansion of all rows of A by `good'' rowspiv`.

Example:

julia> using Random, LinearAlgebra, Maxvol
julia> rng = MersenneTwister(100);
julia> A = rand(rng, BigFloat, 1000, 100);
julia> piv, C = rect_maxvol_generic(A);
julia> norm(A-C*A[piv,:]) / norm(A)
1.487413551535496062888389670275572427766752748825675538705145867354156169433079e-76
julia> A = rand(rng, ComplexF64, 1000, 100);
julia> piv, C = rect_maxvol_generic(A);
julia> norm(A-C*A[piv,:]) / norm(A)
3.5140903782712447e-15

See also: rect_maxvol

rect_maxvol(A, tol=1.0, maxK=size(A,1), min_add_K=0, min_K=size(A,2),
    start_maxvol_iters=10, identity_submatrix=true)

Finds good rectangular submatrix. Uses greedy iterative maximization of 2-volume to find good K-by-r submatrix in a given N-by-r matrix A of rank r. Returns good submatrix and least squares coefficients of expansion (N-by-K matrix) of rows of matrix A by rows of good submatrix.

Uses vendor-optimized LAPACK, provided by Julia. Supports only 4 input types: Float32 (single), Float64 (double), ComplexF32 (single complex) and ComplexF64 (double complex).

Arguments:

• A::Matrix: Input matrix on entry.
• tol::Float64: Stop when volume growth is less or equal to this.
• maxK::Int: Maximum number of rows in good submatrix.
• minK::Int: Minimum number of rows in good submatrix.
• min_add_K::Int: Minimum number of rows to add to the square submatrix. Resulting good matrix will have minimum of r+min_add_K rows.
• start_maxvol_iters::Int: How many iterations of square maxvol (optimization of 1-volume) is required to be done before actual rectangular 2-volume maximization.
• identity_submatrix::Bool: Coefficients of expansions are computed as least squares solution. If identity_submatrix is True, returned matrix of coefficients will have submatrix, corresponding to good rows, set to identity.

Returns:

• piv::Vector{Int}: Indexes of pivoted rows
• C::Matrix: N-by-size(piv) matrix of coefficients of expansion of all rows of A by `good'' rowspiv`.

Example:

julia> using Random, LinearAlgebra, Maxvol
julia> rng = MersenneTwister(100);
julia> A = rand(rng, Float64, 1000, 100);
julia> piv, C = rect_maxvol(A);
julia> norm(A-C*A[piv,:]) / norm(A)
1.8426360389674326e-15
julia> A = rand(rng, ComplexF32, 1000, 100);
julia> piv, C = rect_maxvol(C);
julia> norm(A-C*A[piv,:]) / norm(A)
1.8014168f-6

See also: rect_maxvol_generic