# BasicLU.jl

`BasicLU.LUFactor`

— Type`F = LUFactor(dim::Int64)`

`BasicLU.getfactors`

— Method```
L, U, p, q = getfactors(F::LUFactor) -> L::SparseMatrixCSC{Float64, Int64},
U::SparseMatrixCSC{Float64, Int64},
p::Vector{Int64},
q::Vector{Int64}
```

Extract LU factors after fresh factorization. `L`

is unit lower triangular, `U`

is upper triangular and `p`

and `q`

are permutation vectors such that (ignoring round-off errors) `B[p,q] = L * U`

when matrix `B`

was factorizied.

`BasicLU.maxvolbasis`

— Method```
basis, F = maxvolbasis(A::SparseMatrixCSC{Float64, Int64}; lindeptol::Float64=1e-8,
volumetol::Float64=2.0, maxpass::Int64=2, verbose::Bool=true) -> Vector{Int64}, LUFactor
```

Find a set of column indices for the matrix `AI = [A I]`

such that `AI[:,basis]`

is square and nonsingular and the number of slack columns in the basis is minimum (this is the row rank deficiency of `A`

). Return the vector of column indices of `AI`

which form the basis matrix and a `LUFactor`

which holds a factorization of the basis matrix.

Method: Scale the slack columns of `AI`

by `lindeptol`

and try to find a maximum volume basis for this matrix by making at most `maxpass`

calls to `maxvolume`

. If `verbose`

is true, then print the number of basis updates after each call.

`BasicLU.maxvolume`

— Function`nupdate = maxvolume(F::LUFactor, A::SparseMatrixCSC{Float64, Int64}, basis::Vector{Int64}, volumetol::Float64=2.0) -> Int64`

Given an initial basis such that `A[:,basis]`

is square and nonsingular, make one pass over the nonbasic columns of `A`

and pivot each column into the basis when it increases the absolute value of the determinant of the basis matrix by more than a factor `volumetol`

. On return `basis`

has been updated. Return the number of basis updates performed.

`BasicLU.solve!`

— Method`solve!(F::LUFactor, rhs::SparseVector{Float64, Int64}, trans::Char) -> SparseVector{Float64, Int64}`

Solve linear system with sparse right-hand side. Solution overwrites `rhs`

. `trans`

must be `'T'`

for transposed solve or `'N'`

for forward solve.

`BasicLU.solve!`

— Method`solve!(F::LUFactor, rhs::Vector{Float64}, trans::Char) -> Vector{Float64}`

Solve linear system with dense right-hand side. Solution overwrites `rhs`

. `trans`

must be `'T'`

for transposed solve or `'N'`

for forward solve.

`BasicLU.solve`

— Method`x = solve(F::LUFactor, rhs::SparseVector{Float64, Int64}, trans::Char) -> SparseVector{Float64, Int64}`

Solve linear system with sparse right-hand side. `rhs`

is not modified. `trans`

must be `'T'`

for transposed solve or `'N'`

for forward solve.

`BasicLU.solve`

— Method`x = solve(F::LUFactor, rhs::Vector{Float64}, trans::Char) -> Vector{Float64}`

Solve linear system with dense right-hand side. `rhs`

is not modified. `trans`

must be `'T'`

for transposed solve or `'N'`

for forward solve.

`BasicLU.solve_for_update`

— Method`solve_for_update(F::LUFactor, pos::Int64; getsol::Bool=false) -> SparseVector{Float64, Int64}`

Solve transposed system in preparation to update the factorization. `pos`

holds the column index of the factorized matrix to be replaced in the next call to `update`

. When `getsol = true`

, then the solution from the transposed solve with a unit vector as right-hand side is returned. Otherwise only the update is prepared.

`BasicLU.solve_for_update`

— Method`solve_for_update(F::LUFactor, newcol::SparseVector{Float64, Int64}; getsol::Bool=false) -> SparseVector{Float64, Int64}`

Solve forward system in preparation to update the factorization. `newcol`

holds the column to be inserted into the factorized matrix in the next call to `update`

. When `getsol = true`

, then the solution from the forward solve with right-hand side `newcol`

is returned. Otherwise only the update is prepared.

`BasicLU.update`

— Method`update(F::LUFactor, pivot::Float64) -> Float64`

Update the factorization after a column modification. The column position and the new column must have been set in previous calls to `solve_for_update`

.

`pivot`

is the pivot element corresponding to the update operation; i.e. when column `j`

of `B`

is to be replaced by vector `v`

, then `pivot = (B\v)[j]`

. The absolute difference between `pivot`

and a recomputed version can be obtained with `getinfo(F, :pivotError)`

; this is also the return value. A pivot error larger than 1e-8, say, indicates numerical instability and suggests refactorization.

An error is thrown when the recomputed pivot element is below the absolute pivot tolerance. In this case no update is performed and the old factorization remains valid.

`BasicLU.update`

— Method`update(F::LUFactor, pos::Int, newcol::SparseVector) -> (lhs, piverr)`

Update the factorization by inserting column `newcol`

at index `pos`

.

`BasicLU.update_retcode`

— Method`update_retcode(F::LUFactor, pivot::Float64) -> (retcode, piverr)`

Similar to `update(F, pivot)`

but returns the return code from BasicLU so that users can handle them.

`BasicLU.update_retcode`

— Method`update_retcode(F::LUFactor, pos::Int, newcol::SparseVector) -> (retcode, lhs, piverr)`

Similar to `update_retcode(F, pos, newcol)`

but returns the code from BasicLU so that users can handle them.

`LinearAlgebra.factorize`

— Method`factorize(F::LUFactor, B::SparseMatrixCSC{Float64, Int64}; check::Bool=true)`

Factorize sparse matrix `B`

, which must be square and have the dimension for which `F`

was created.

The factorization method stops when all elements of the active submatrix are below the absolute pivot tolerance. In this case the `L`

and `U`

matrix are padded with columns of the identity matrix, yielding the factorization of a matrix `B*`

which equals `B`

except that the dependent columns are replaced by columns of the identity matrix. The number of actual pivot steps performed can be obtained with `getinfo(F, :nPivot)`

.

When `check = true`

, an error is thrown if the number of pivot steps is less than the dimension of `B`

.