/
sparse_matrix.go
150 lines (116 loc) · 3.44 KB
/
sparse_matrix.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package mat
import (
"github.com/angelsolaorbaiceta/inkmath/vec"
)
// A SparseMat is a matrix where the zeroes aren't stored.
type SparseMat struct {
rows, cols int
data map[int]map[int]float64
}
// MakeSquareSparse creates a new square sparse matrix with the given number of rows and columns.
func MakeSquareSparse(size int) *SparseMat {
return MakeSparse(size, size)
}
// MakeSparse creates a new sparse matrix with the given number of rows and columns.
func MakeSparse(rows, cols int) *SparseMat {
return &SparseMat{rows, cols, make(map[int]map[int]float64)}
}
/*
MakeSparseWithData creates a new sparse matrix initialized with the given data.
This method is mainly used for testing purposes as it makes no sense to create a sparse
matrix with a given data slice. Most of the elements in a sparse matrix should be zero.
*/
func MakeSparseWithData(rows, cols int, data []float64) *SparseMat {
matrix := MakeSparse(rows, cols)
FillMatrixWithData(matrix, data)
return matrix
}
/*
MakeIdentity creates a new sparse matrix with all zeroes except in the main diagonal,
which has ones.
*/
func MakeIdentity(size int) *SparseMat {
identity := MakeSparse(size, size)
for i := 0; i < size; i++ {
identity.SetValue(i, i, 1.0)
}
return identity
}
// Rows returns the number of rows in the matrix.
func (m SparseMat) Rows() int { return m.rows }
// Cols returns the number of columns in the matrix.
func (m SparseMat) Cols() int { return m.cols }
// Value returns the value at a given row and column.
func (m SparseMat) Value(row, col int) float64 {
if dataRow, hasRow := m.data[row]; hasRow {
if value, hasValue := dataRow[col]; hasValue {
return value
}
}
return 0.0
}
// NonZeroIndicesAtRow returns a slice with all non-zero elements indices for the given row.
func (m SparseMat) NonZeroIndicesAtRow(row int) []int {
if dataRow, hasRow := m.data[row]; hasRow {
var (
keys = make([]int, len(m.data[row]))
i = 0
)
for k := range dataRow {
keys[i] = k
i++
}
return keys
}
return []int{}
}
// TimesVector multiplies this matrix and a vector.
func (m SparseMat) TimesVector(vector vec.ReadOnlyVector) vec.ReadOnlyVector {
if m.cols != vector.Length() {
panic("Can't multiply matrix and vector due to size mismatch")
}
result := vec.Make(m.rows)
for rowIndex := range m.data {
result.SetValue(rowIndex, m.rowTimesVector(rowIndex, vector))
}
return result
}
// TimesMatrix multiplies this matrix times other.
func (m SparseMat) TimesMatrix(other ReadOnlyMatrix) ReadOnlyMatrix {
if m.cols != other.Rows() {
panic("Can't multiply matrices due to size mismatch")
}
var (
rows = m.rows
cols = other.Cols()
sum float64
result = MakeSparse(rows, cols)
)
for i, row := range m.data {
for j := 0; j < cols; j++ {
sum = 0.0
for k, val := range row {
sum += val * other.Value(k, j)
}
result.SetValue(i, j, sum)
}
}
return result
}
// RowTimesVector returns the result of multiplying the row at the given index times the given vector.
func (m SparseMat) RowTimesVector(row int, vector vec.ReadOnlyVector) float64 {
if m.cols != vector.Length() {
panic("Can't multiply matrix row with vector due to size mismatch")
}
return m.rowTimesVector(row, vector)
}
func (m SparseMat) rowTimesVector(row int, vector vec.ReadOnlyVector) float64 {
if rowData, hasRow := m.data[row]; hasRow {
result := 0.0
for i, val := range rowData {
result += vector.Value(i) * val
}
return result
}
return 0.0
}