Class: SparseMatrix::YaleSparseMatrix

Inherits:
Object
  • Object
show all
Defined in:
lib/sparsematrix/yale.rb

Overview

The Yale sparse matrix format stores an initial sparse ‘m` x `n` matrix, `M`, in row form using three (one-dimensional) arrays (`A`, `IA`, `JA`). Let `NNZ` denote the number of nonzero entries in `M`. (Note that zero-based indices shall be used here.)

  • The array ‘A` is of length `NNZ` and holds all the nonzero entries of `M` in left-to-right top-to-bottom (“row-major”) order.

  • The array ‘IA` is of length `m + 1` and contains the index in `A` of the first element in each row, followed by the total number of nonzero elements `NNZ`. `IA` contains the index in `A` of the first nonzero element of row `i`. Row `i` of the original matrix extends from `A[IA]` to `A[IA[i + 1] - 1]`, i.e. from the start of one row to the last index before the start of the next. The last entry, `IA`, must be the number of elements in `A`.

  • The third array, ‘JA`, contains the column index in `M` of each element of `A` and hence is of length `NNZ` as well.

For example, the matrix

0 0 0 0
5 8 0 0
0 0 3 0
0 6 0 0

is a 4 x 4 matrix with 4 nonzero elements, hence

A  = [ 5 8 3 6 ]
IA = [ 0 0 2 3 4 ]
JA = [ 0 1 2 1 ]

So, in array ‘JA`, the element “5” from `A` has column index 0, “8” and “6” have index 1, and element “3” has index 2.

In this case the Yale representation contains 13 entries, compared to 16 in the original matrix. The Yale format saves on memory only when ‘NNZ < (m (n - 1) - 1) / 2`. Another example, the matrix

10 20  0  0  0  0
 0 30  0 40  0  0
 0  0 50 60 70  0
 0  0  0  0  0 80

is a 4 x 6 matrix (24 entries) with 8 nonzero elements, so

A  = [ 10 20 30 40 50 60 70 80 ]
IA = [ 0 2 4 7 8 ]
JA = [ 0 1 1 3 2 3 4 5 ]

The whole is stored as 21 entries.

‘IA` splits the array `A` into rows: `(10, 20) (30, 40) (50, 60, 70) (80)`; `JA` aligns values in columns: `(10, 20, …) (0, 30, 0, 40, …)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80)`. Note that in this format, the first value of `IA` is always zero and the last is always `NNZ`, so they are in some sense redundant. However, they can make accessing and traversing the array easier for the programmer.

en.wikipedia.org/wiki/Sparse_matrix#Yale

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(zero = nil) ⇒ YaleSparseMatrix

Returns a new instance of YaleSparseMatrix.

Parameters:

  • zero (defaults to: nil) —

    The value to return for zero / unused elements



75
76
77
78
79
80
 
# File 'lib/sparsematrix/yale.rb', line 75

def initialize(zero = nil)
  @zero = zero
  @elements = []
  @row_index = [0]
  @index_column = []
end

Instance Attribute Details

#elements ⇒ Object (readonly) Also known as: a

Returns the value of attribute elements.



81
82
83
 
# File 'lib/sparsematrix/yale.rb', line 81

def elements
  @elements
end

#index_column ⇒ Object (readonly) Also known as: ja

Returns the value of attribute index_column.



81
82
83
 
# File 'lib/sparsematrix/yale.rb', line 81

def index_column
  @index_column
end

#row_index ⇒ Object (readonly) Also known as: ia

Returns the value of attribute row_index.



81
82
83
 
# File 'lib/sparsematrix/yale.rb', line 81

def row_index
  @row_index
end

#zero ⇒ Object (readonly)

Returns the value of attribute zero.



81
82
83
 
# File 'lib/sparsematrix/yale.rb', line 81

def zero
  @zero
end

Class Method Details

.build(zero, rows, columns, &block) ⇒ Object 



62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/sparsematrix/yale.rb', line 62

def self.build(zero, rows, columns, &block)
  return enum_for :build, rows, columns unless block_given?
  smx = new zero
  rows.times do |row|
    columns.times do |column|
      value = yield row, column
      smx[row, column] = value unless value == zero
    end
  end
  smx
end

Instance Method Details

#==(other) ⇒ Boolean

Compares two SparseMatrix’s for equality

Parameters:

Returns:

  • (Boolean) 


133
134
135
136
137
138
139
 
# File 'lib/sparsematrix/yale.rb', line 133

def ==(other)
  return false unless other.is_a? YaleSparseMatrix
  nonzero_element_count == other.nonzero_element_count &&
    elements == other.elements &&
    row_index == other.row_index &&
    index_column == other.index_column
end

#[](row, column) ⇒ Object Also known as: element, component

Returns the element at the given index, or #zero.

Parameters:

  • row (Numeric) —

    row part of the index to return

  • column (Numeric) —

    column part of the index to return

Returns:

  • the element at the given index, or #zero



91
92
93
94
95
 
# File 'lib/sparsematrix/yale.rb', line 91

def [](row, column)
  index = element_index row, column
  return zero unless index
  elements[index]
end

#[]=(row, column, value) ⇒ Object

Returns the value that was passed in.

Parameters:

  • row (Numeric) —

    row part of the index to set

  • column (Numeric) —

    column part of the index to set

  • value —

    the value to set

Returns:

  • the value that was passed in



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
 
# File 'lib/sparsematrix/yale.rb', line 103

def []=(row, column, value)
  if row >= row_count
    add_rows(row - row_count + 1)
  end

  index = row_start = row_index[row]
  row_end = row_index[row + 1]

  while index < row_end
    current_column = index_column[index]
    if current_column == column
      @elements[index] = value
      return value
    end
    break if current_column > column
    index += 1
  end

  @elements.insert(index, value)
  @index_column.insert(index, column)
  while row < row_count
    row += 1
    @row_index[row] += 1
  end
  value
end

#collect(&block) ⇒ YaleSparseMatrix Also known as: map

Returns a new SparseMatrix whos elements have been mapped through the supplied block.

Parameters:

  • block

Returns:

  • (YaleSparseMatrix) —

    a new SparseMatrix whos elements have been mapped through the supplied block



144
145
146
147
 
# File 'lib/sparsematrix/yale.rb', line 144

def collect(&block)
  return enum_for :collect unless block_given?
  clone.instance_eval { @elements.collect(&block) }
end

#column_count ⇒ Numeric Also known as: n

Returns The number of columns in the matrix.

Returns:

  • (Numeric) —

    The number of columns in the matrix



151
152
153
154
 
# File 'lib/sparsematrix/yale.rb', line 151

def column_count
  row_index
  index_column.last + 1
end

#density ⇒ Object Also known as: sparsity

Returns the density of the SparseMatrix; that is, how many elements are non-zero divided by the total size of the matrix.

Returns:

  • the density of the SparseMatrix; that is, how many elements are non-zero divided by the total size of the matrix



159
160
161
 
# File 'lib/sparsematrix/yale.rb', line 159

def density
  nonzero_element_count / (row_count * column_count * 1.0)
end

#each(zeroes = false, &block) ⇒ YaleSparseMatrix

Passes each element of the matrix to the supplied block

Parameters:

  • block

Returns:



167
168
169
170
171
172
173
174
175
176
177
178
179
 
# File 'lib/sparsematrix/yale.rb', line 167

def each(zeroes = false, &block)
  return enum_for :each, zeroes unless block_given?
  if zeroes
    row_count.times do |row|
      column_count.times do |col|
        yield self[row, col]
      end
    end
  else
    @elements.each(&block)
  end
  self
end

#each_with_index(zeroes = false, &_block) ⇒ YaleSparseMatrix

Passes each element of the matrix and its index to the supplied block

Parameters:

  • block

Returns:



184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/sparsematrix/yale.rb', line 184

def each_with_index(zeroes = false, &_block)
  return enum_for :each_with_index, zeroes unless block_given?
  if zeroes
    row_count.times do |row|
      column_count.times do |_col|
        element = self[row, column]
        yield [element, row, column]
      end
    end
  else
    ia.each_cons(2).each_with_index do |indexes, row|
      row_start, row_end = *indexes
      a[row_start...row_end].each_with_index do |element, index|
        yield [element, row, ja[row_start + index]]
      end
    end
  end
end

#empty? ⇒ Boolean Also known as: zero?

Returns true if the matrix is empty; i.e. if #nonzero_element_count is 0

Returns:

  • (Boolean) 


205
206
207
 
# File 'lib/sparsematrix/yale.rb', line 205

def empty?
  nonzero_element_count == 0
end

#include?(element) ⇒ Boolean

Returns true if the matrix includes element

Parameters:

  • element

Returns:

  • (Boolean) 


213
214
215
 
# File 'lib/sparsematrix/yale.rb', line 213

def include?(element)
  @elements.include? element
end

#index(element) ⇒ Array(Numeric, Numeric)?

Returns the index of element in the matrix, or nil

Parameters:

  • element

Returns:

  • (Array(Numeric, Numeric), nil) 


220
221
222
223
 
# File 'lib/sparsematrix/yale.rb', line 220

def index(element)
  each_with_index { |e, index| return index if e == element }
  nil
end

#inspect(zeroes = false) ⇒ Object 



225
226
227
228
229
230
231
232
233
234
 
# File 'lib/sparsematrix/yale.rb', line 225

def inspect(zeroes = false)
  "#{self.class}[\n" +
    row_count.times.map do |row|
      column_count.times.map { |col| self[row, col] }
        .reject { |e| !zeroes && e == zero }.inspect
    end.join(",\n") +
    '] # ' \
    "#{saving_memory? ? 'efficient' : 'not efficient'} " \
    "#{format '%.02f', density * 100.0}% density"
end

#nonzero_element_count ⇒ Numeric Also known as: nnz

The number of non-zero elements in the matrix

Returns:

  • (Numeric) 


238
239
240
 
# File 'lib/sparsematrix/yale.rb', line 238

def nonzero_element_count
  @row_index.last
end

#row_count ⇒ Numeric Also known as: m

The number of rows in the matrix

Returns:

  • (Numeric) 


245
246
247
 
# File 'lib/sparsematrix/yale.rb', line 245

def row_count
  row_index.length - 1
end

#saving_memory? ⇒ Boolean

Returns true if the SparseMatrix uses less memory than a naive matrix

Returns:

  • (Boolean) 


252
253
254
 
# File 'lib/sparsematrix/yale.rb', line 252

def saving_memory?
  nnz < (m * (n - 1) - 1) / 2
end