gpz

Documentation

Overview

Package gp provides sparse LU factorization with partial pivoting.

The algorithm is described in "Sparse Partial Pivoting in Time Proportional to Arithmetic Operations" by John R. Gilbert and Tim Peierls.

@article{Gilbert1988,
  doi = {10.1137/0909058},
  url = {https://doi.org/10.1137/0909058},
  year  = {1988},
  month = {sep},
  publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
  volume = {9},
  number = {5},
  pages = {862--874},
  author = {John R. Gilbert and Tim Peierls},
  title = {Sparse Partial Pivoting in Time Proportional to Arithmetic Operations},
  journal = {SIAM Journal on Scientific and Statistical Computing}
}

This package is translated from the gp FORTRAN code distributed in Sivan Toledo's work on incomplete-factorization, from PARC in the early 1990s, as published in the ILU package on Netlib:

http://www.netlib.org/linalg/ilu.tgz

This source code is distributed, with the kind permission of John Gilbert and Tim Peierls, under a 3-clause BSD license.

Index

• Variables
• func Solve(lu *LU, rhs [][]complex128, trans bool) error
• type LU
  • func Factor(nA int, rowind, colptr []int, nzA []complex128, optFuncs ...OptFunc) (*LU, error)
• type OptFunc
  • func ColFillRatio(colFillRatio float64) OptFunc
  • func ColPerm(colPerm []int) OptFunc
  • func DropThreshold(dropThreshold float64) OptFunc
  • func ExpandRatio(expandRatio float64) OptFunc
  • func FillRatio(fillRatio float64) OptFunc
  • func PartialPivoting(pivotThreshold float64) OptFunc
  • func ThresholdPivoting() OptFunc
  • func WithoutPivoting() OptFunc

Variables

var Logger io.Writer

Logger is a writer used for logging messages.

Functions

func Solve

func Solve(lu *LU, rhs [][]complex128, trans bool) error

Solve Ax=b for one or more right-hand-sides given the numeric factorization of A from Factor.

Types

type LU

type LU struct {
	// contains filtered or unexported fields
}

LU is a lower-upper numeric factorization.

func Factor

func Factor(nA int, rowind, colptr []int, nzA []complex128, optFuncs ...OptFunc) (*LU, error)

Factor performs sparse LU factorization with partial pivoting.

Given a matrix A in sparse format by columns, it performs an LU factorization, with partial or threshold pivoting, if desired. The factorization is PA = LU, where L and U are triangular. P, L, and U are returned. This subroutine uses the Coleman-Gilbert-Peierls algorithm, in which total time is O(nonzero multiplications).

type OptFunc

type OptFunc func(*options) error

func ColFillRatio

func ColFillRatio(colFillRatio float64) OptFunc

ColFillRatio sets the column fill ratio. If < 0 the column fill ratio is not limited. Default value is -1.

func ColPerm

func ColPerm(colPerm []int) OptFunc

ColPerm sets the column permutation vector. If nil natural ordering will be used.

func DropThreshold

func DropThreshold(dropThreshold float64) OptFunc

DropThreshold sets drop tolerance.

For each major step of the algorithm, the pivot is chosen to be a nonzero below the diagonal in the current column of A with the most nonzeros to the right in its row, with absolute value at least dropThreshold*maxpiv, where maxpiv is the largest absolute value below the diagonal in the current column. Note that if dropThreshold <= 0.0, then the pivot is chosen purely on the basis of row sparsity. Also, if dropThreshold >= 1.0, then the pivoting is effectively partial pivoting with ties broken on the basis of sparsity.

func ExpandRatio

func ExpandRatio(expandRatio float64) OptFunc

ExpandRatio sets the ratio for LU size growth. Default value is 1.2.

func FillRatio

func FillRatio(fillRatio float64) OptFunc

FillRatio sets the ratio of the initial LU size to NNZ. Default value is 4.

func PartialPivoting

func PartialPivoting(pivotThreshold float64) OptFunc

PartialPivoting enables partial pivoting. Enabled by default. pivotThreshold is the fraction of max pivot candidate acceptable for pivoting. Default value is 1.

func ThresholdPivoting

func ThresholdPivoting() OptFunc

ThresholdPivoting enables threshold pivoting.

func WithoutPivoting

func WithoutPivoting() OptFunc

WithoutPivoting disables pivoting.