sparse

package module
v0.0.0-...-a1023c2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 7, 2020 License: LGPL-2.1 Imports: 9 Imported by: 1

README

sparse

codecov Build Status Go Report Card GitHub license GoDoc

This package based on program CSparse from SuiteSparse 5.4.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-4         	   37153	     30785 ns/op	   51328 B/op	      28 allocs/op
BenchmarkLU/Dense_:__30:__300-4         	   41449	     29516 ns/op	    9236 B/op	      11 allocs/op
BenchmarkLU/Sparse:_100:_1070-4         	    9572	    108839 ns/op	  201328 B/op	      28 allocs/op
BenchmarkLU/Dense_:_100:_1070-4         	    4323	    233880 ns/op	   85005 B/op	      11 allocs/op
BenchmarkLU/Sparse:_300:_3270-4         	    3404	    324523 ns/op	  566384 B/op	      28 allocs/op
BenchmarkLU/Dense_:_300:_3270-4         	     476	   2494250 ns/op	  739173 B/op	      20 allocs/op
BenchmarkLU/Sparse:1000:10970-4         	    1029	   1065713 ns/op	 1794812 B/op	      28 allocs/op
BenchmarkLU/Dense_:1000:10970-4         	      18	  63434980 ns/op	 8061283 B/op	      47 allocs/op
BenchmarkLU/Sparse:3000:32970-4         	     378	   3206861 ns/op	 5382921 B/op	      28 allocs/op
BenchmarkLU/Dense_:3000:32970-4         	       2	 802618764 ns/op	72295580 B/op	     111 allocs/op

Using sparse algorithm is effective in test case for square matrixes with size more 50.

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 CSparse is exist on page.
  • Download new version.
  • Compare file-by-file with file in folder CSparse of 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.lnz and css.unz is not float type double, better to use integer type like int.

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Dupl 

func Dupl(A *Matrix) error

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)
}
fmt.Fprintln(os.Stdout, "Before:")
A.Print(os.Stdout, false)
err = Dupl(A)
if err != nil {
	panic(err)
}
fmt.Fprintln(os.Stdout, "After:")
A.Print(os.Stdout, 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 

func Entry(T *Triplet, i, j int, x float64) error

Entry - add an entry to a triplet matrix; return 1 if ok, 0 otherwise

Name function in CSparse : cs_entry.

func Fkeep 

func Fkeep(A *Matrix, fkeep func(i int, j int, x float64) bool) (_ int, err error)

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 

func Gaxpy(A *Matrix, x []float64, y []float64, errorIgnore ...bool) error

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]

func IsSym 

func IsSym(A *Matrix) (ok bool, err error)

IsSym return true if matrix A is symmetrical

func Norm 

func Norm(A *Matrix) float64

Norm - 1-norm of a sparse matrix = max (sum (abs (A))), largest column sum

Name function in CSparse : cs_norm.

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(os.Stdout, false)

	// compress
	A, err := sparse.Compress(T)
	if err != nil {
		panic(err)
	}
	A.Print(os.Stdout, 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)
	}
	A.Print(os.Stdout, false)
	fmt.Fprintf(os.Stdout, "Result = %v", x)

}

Output:

Sparse
triplet: 2-by-2, nzmax: 4 nnz: 4
    0 0 : 1.000000e+00
    0 1 : 5.000000e+00
    1 0 : 2.000000e+00
    1 1 : 3.000000e+00
Sparse
2-by-2, nzmax: 4 nnz: 4, 1-norm: 8.000000e+00
    col 0 : locations 0 to 1
      0 : 1.000000e+00
      1 : 2.000000e+00
    col 1 : locations 2 to 3
      0 : 5.000000e+00
      1 : 3.000000e+00
Sparse
2-by-2, nzmax: 4 nnz: 4, 1-norm: 8.000000e+00
    col 0 : locations 0 to 1
      0 : 1.000000e+00
      1 : 2.000000e+00
    col 1 : locations 2 to 3
      0 : 5.000000e+00
      1 : 3.000000e+00
Result = [1 2]

func (*LU) Factorize 

func (lu *LU) Factorize(A *Matrix, ignore ...int) error

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) Order 

func (lu *LU) Order(order Order)

func (*LU) Solve 

func (lu *LU) Solve(b []float64) (x []float64, _ error)

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 

func Add(A *Matrix, B *Matrix, α float64, β float64) (*Matrix, error)

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)
}
R.Print(os.Stdout, 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 

func Compress(T *Triplet) (_ *Matrix, err error)

Compress - compress triplet matrix T to compressed sparse column(CSC) format.

Name function in CSparse : cs_compress.

func Multiply 

func Multiply(A *Matrix, B *Matrix) (*Matrix, error)

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)
}
AT, err := Transpose(A)
if err != nil {
	panic(err)
}
M, err := Multiply(A, AT)
if err != nil {
	panic(err)
}
M.Print(os.Stdout, 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

func Transpose 

func Transpose(A *Matrix) (*Matrix, error)

Transpose - C = A'

Name function in CSparse : cs_transpose.

func (*Matrix) Copy 

func (A *Matrix) Copy() (*Matrix, error)

func (*Matrix) Dims 

func (m *Matrix) Dims() (rows, columns int)

Size return size of matrix

func (*Matrix) IsTriplet 

func (A *Matrix) IsTriplet() bool

func (*Matrix) Print 

func (A *Matrix) Print(out io.Writer, brief bool) error

Print - print a sparse matrix. 

if brief is true, then print shortly

Name function in CSparse : cs_print.

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
)

func (Order) String 

func (o Order) String() (out string)

type Triplet 

type Triplet Matrix

func Load 

func Load(f io.Reader) (T *Triplet, err error)

Load - load a triplet matrix from a file.

Name function in CSparse : cs_load.

func NewTriplet 

func NewTriplet() (*Triplet, error)

func (*Triplet) Print 

func (A *Triplet) Print(out io.Writer, brief bool) error

Print triplets of matrix 

if brief is true, then print shortly

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.