README
¶
sparse
This package based on program CSparse from SuiteSparse 5.3.0
Comparation with gonum.mat.LU
go test -v -cpuprofile cpu.prof -memprofile mem.prof -coverprofile=coverage.out -run=BenchmarkLU -bench=BenchmarkLU -benchmem
# goos: linux
# goarch: amd64
# pkg: github.com/Konstantin8105/sparse
# BenchmarkLU/Sparse:__30:__300-6 50000 34007 ns/op 51456 B/op 32 allocs/op
# BenchmarkLU/Dense_:__30:__300-6 50000 30012 ns/op 9249 B/op 11 allocs/op
# BenchmarkLU/Sparse:_100:_1070-6 10000 125092 ns/op 201458 B/op 32 allocs/op
# BenchmarkLU/Dense_:_100:_1070-6 5000 241981 ns/op 85261 B/op 11 allocs/op
# BenchmarkLU/Sparse:_300:_3270-6 5000 354187 ns/op 566515 B/op 32 allocs/op
# BenchmarkLU/Dense_:_300:_3270-6 500 2377480 ns/op 746151 B/op 22 allocs/op
# BenchmarkLU/Sparse:1000:10970-6 1000 1152972 ns/op 1794937 B/op 32 allocs/op
# BenchmarkLU/Dense_:1000:10970-6 20 86145264 ns/op 8079531 B/op 54 allocs/op
# BenchmarkLU/Sparse:3000:32970-6 500 3320653 ns/op 5383122 B/op 32 allocs/op
# BenchmarkLU/Dense_:3000:32970-6 1 1328677635 ns/op 72346808 B/op 156 allocs/op
Using sparse algorithm is effective in test case for square matrixes with size more 100.
Example of comparing CSparse and CXSparse
rm -rf /tmp/CXSparse
cp -R ./CXSparse/ /tmp/
sed -i 's/CS_ENTRY/double/g' /tmp/CXSparse/Source/*.c
sed -i 's/CS_INT/csi/g' /tmp/CXSparse/Source/*.c
meld /tmp/CXSparse/ ./CSparse/
How updating package
- Check new version of
CSparseis exist on page. - Download new version.
- Compare file-by-file with file in folder
CSparseof that package. - Inject changes into Go files of package.
Note: CSparse haven`t any updates at the last few years, so that package is actual at the future.
Just for information
This package transpiled CSparse from C to Go by c4go.
Profiling
go test -v -cpuprofile=cpu.prof -memprofile=mem.prof -run=Benchmark -bench=Benchmark -benchmem
go tool pprof cpu.prof
go tool pprof mem.prof
Coverage
go test -coverprofile=coverage.out -run=TestLU
go tool cover -html=coverage.out
Questions for CSparse
- Variables
css.lnzandcss.unzis not float typedouble, better to use integer type likeint.
Documentation
¶
Index ¶
- func Dupl(A *Matrix) error
- func Entry(T *Triplet, i, j int, x float64) error
- func Fkeep(A *Matrix, fkeep func(i int, j int, x float64) bool) (_ int, err error)
- func Gaxpy(A *Matrix, x []float64, y []float64) error
- func IsSym(A *Matrix) (ok bool, err error)
- func Norm(A *Matrix) float64
- type LU
- type Matrix
- type Order
- type Triplet
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Dupl ¶
Dupl - remove duplicate entries from A
Name function in CSparse: cs_dupl
Example ¶
var stdin bytes.Buffer
stdin.WriteString(" 1 0 10\n 0 0 1\n 1 1 4\n 1 0 3\n 0 1 2\n 0 0 1 ")
T, err := Load(&stdin)
if err != nil {
panic(err)
}
A, err := Compress(T)
if err != nil {
panic(err)
}
osStdout = os.Stdout // for output in standart stdout
fmt.Fprintln(os.Stdout, "Before:")
A.Print(false)
err = Dupl(A)
if err != nil {
panic(err)
}
fmt.Fprintln(os.Stdout, "After:")
A.Print(false)
Output: Before: Sparse 2-by-2, nzmax: 6 nnz: 6, 1-norm: 1.500000e+01 col 0 : locations 0 to 3 1 : 1.000000e+01 0 : 1.000000e+00 1 : 3.000000e+00 0 : 1.000000e+00 col 1 : locations 4 to 5 1 : 4.000000e+00 0 : 2.000000e+00 After: Sparse 2-by-2, nzmax: 4 nnz: 4, 1-norm: 1.500000e+01 col 0 : locations 0 to 1 1 : 1.300000e+01 0 : 2.000000e+00 col 1 : locations 2 to 3 1 : 4.000000e+00 0 : 2.000000e+00
func Entry ¶
Entry - add an entry to a triplet matrix; return 1 if ok, 0 otherwise
Name function in CSparse : cs_entry.
func Fkeep ¶
Fkeep - drop entries for which fkeep(A(i,j)) is false; return nz if OK, else -1 and error Name function of CSparse: cs_fkeep
func Gaxpy ¶
Gaxpy - calculate by next formula.
Matrix A is sparse matrix in CSC format.
y = A*x+y
Name function in CSparse : cs_gaxpy.
Example ¶
var s bytes.Buffer
s.WriteString("0 0 1\n1 0 3\n2 0 5\n0 1 2\n1 1 4\n2 1 6")
T, err := Load(&s)
if err != nil {
panic(err)
}
A, err := Compress(T)
if err != nil {
panic(err)
}
x := []float64{7, 8}
y := []float64{9, 10, 11}
fmt.Fprintln(os.Stdout, "Vector `y` before:")
fmt.Fprintln(os.Stdout, y)
err = Gaxpy(A, x, y)
if err != nil {
panic(err)
}
fmt.Fprintln(os.Stdout, "Vector `y` before:")
fmt.Fprintln(os.Stdout, y)
Output: Vector `y` before: [9 10 11] Vector `y` before: [32 63 94]
Types ¶
type LU ¶
type LU struct {
// contains filtered or unexported fields
}
LU is a type for creating and using the LU factorization of a matrix.
Example ¶
package main
import (
"fmt"
"math"
"os"
"github.com/Konstantin8105/sparse"
)
func main() {
// Solve next:
// [ 1 5 ] [ x1 ] = [ 11 ]
// [ 2 3 ] [ x2 ] [ 8 ]
T, err := sparse.NewTriplet()
if err != nil {
panic(err)
}
// storage
errs := []error{
sparse.Entry(T, 0, 0, 1),
sparse.Entry(T, 0, 1, 5),
sparse.Entry(T, 1, 0, 2),
sparse.Entry(T, 1, 1, 3),
}
for i := range errs {
if errs[i] != nil {
panic(errs[i])
}
}
T.Print(false)
// compress
A, err := sparse.Compress(T)
if err != nil {
panic(err)
}
A.Print(false)
// singinal check
min, max := math.MaxFloat64, 0.0
_, err = sparse.Fkeep(A, func(i, j int, x float64) bool {
if i == j { // diagonal
if math.Abs(x) > max {
max = math.Abs(x)
}
if math.Abs(x) < min {
min = math.Abs(x)
}
}
// keep entry
return true
})
if err != nil {
panic(err)
}
if min == 0 {
panic("singular: zero entry on diagonal")
}
if max/min > 1e18 {
panic(fmt.Sprintf("singular: max/min diagonal entry: %v", max/min))
}
// solving
lu := new(sparse.LU)
err = lu.Factorize(A)
if err != nil {
panic(err)
}
b := []float64{11, 8}
x, err := lu.Solve(b)
if err != nil {
panic(err)
}
fmt.Fprintf(os.Stdout, "%v", x)
}
Output: [1 2]
func (*LU) Factorize ¶
Factorize computes the LU factorization of the matrix a and stores the result. Input matrix A is not checked on singular error. List `ignore` is list of ignore row and column in calculation.
func (*LU) Solve ¶
Solve solves a system of linear equations using the LU decomposition of a matrix A.
A * x = b
Output vector `x` have same length of vector `b`. Length of vector `b` have 2 acceptable cases:
1) if length of vector b is matrix rows length factorized matrix A then for ignored rows added values `0.0`.
2) length of vector b is matrix rows length factorized matrix A minus length of ignore list.
type Matrix ¶
type Matrix struct {
// contains filtered or unexported fields
}
Matrix - sparse matrix. Matrix in compressed-column or triplet fotmat.
Name struct in CSparse : cs or cs_sparse
func Add ¶
Add - additon two sparse matrix with factors.
Matrix A, B is sparse matrix in CSC format.
C = α*A + β*B
Name function in CSparse : cs_add.
Example ¶
var stdin bytes.Buffer
stdin.WriteString("0 0 1\n0 1 2\n1 0 3\n1 1 4")
T, err := Load(&stdin)
if err != nil {
panic(err)
}
A, err := Compress(T)
if err != nil {
panic(err)
}
AT, err := Transpose(A)
if err != nil {
panic(err)
}
R, err := Add(A, AT, 1, 2)
if err != nil {
panic(err)
}
osStdout = os.Stdout // for output in standart stdout
R.Print(false)
Output: Sparse 2-by-2, nzmax: 4 nnz: 4, 1-norm: 2.000000e+01 col 0 : locations 0 to 1 0 : 3.000000e+00 1 : 7.000000e+00 col 1 : locations 2 to 3 0 : 8.000000e+00 1 : 1.200000e+01
func Compress ¶
Compress - compress triplet matrix T to compressed sparse column(CSC) format.
Name function in CSparse : cs_compress.
func Multiply ¶
Multiply - C = A*B
Name function in CSparse : cs_multiply.
Example ¶
var stdin bytes.Buffer
stdin.WriteString(" 1 0 10\n 0 0 1\n 1 1 4\n 1 0 3\n 0 1 2\n 0 0 1 ")
T, err := Load(&stdin)
if err != nil {
panic(err)
}
A, err := Compress(T)
if err != nil {
panic(err)
}
osStdout = os.Stdout // for output in standart stdout
AT, err := Transpose(A)
if err != nil {
panic(err)
}
M, err := Multiply(A, AT)
if err != nil {
panic(err)
}
M.Print(false)
Output: Sparse 2-by-2, nzmax: 4 nnz: 4, 1-norm: 2.190000e+02 col 0 : locations 0 to 1 1 : 3.400000e+01 0 : 8.000000e+00 col 1 : locations 2 to 3 1 : 1.850000e+02 0 : 3.400000e+01
type Order ¶
type Order uint8
const ( // natural ordering. AmdNatural Order = iota // matrix is square. Used for Cholesky or LU factorization of a matrix with // entries preliminary on the diagonal and a preliminary symmetric // nonzero pattern. // // amd(A+A') AmdChol // usually used for LU factorization of unsymmetric matrices. // // amd(S'*S) AmdLU // usually used for LU or QR factorization. // // amd(A'*A) AmdQR )
Source Files