class SparseMatrix::YaleSparseMatrix

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

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

Attributes

a[R]
elements[R]
ia[R]
index_column[R]
ja[R]
row_index[R]
zero[R]

Public Class Methods

build(zero, rows, columns) { |row, column| ... } click to toggle source
# 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
new(zero = nil) click to toggle source

@param zero The value to return for zero / unused elements

# File lib/sparsematrix/yale.rb, line 75
def initialize(zero = nil)
  @zero = zero
  @elements = []
  @row_index = [0]
  @index_column = []
end

Public Instance Methods

==(other) click to toggle source

Compares two SparseMatrix's for equality @param other [YaleSparseMatrix] @return [Boolean]

# 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) click to toggle source

@param row [Numeric] row part of the index to return @param column [Numeric] column part of the index to return @return the element at the given index, or zero

# File lib/sparsematrix/yale.rb, line 91
def [](row, column)
  index = element_index row, column
  return zero unless index
  elements[index]
end
Also aliased as: element, component
[]=(row, column, value) click to toggle source

@param row [Numeric] row part of the index to set @param column [Numeric] column part of the index to set @param value the value to set @return the value that was passed in

# 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) click to toggle source

@param block @return [YaleSparseMatrix] a new SparseMatrix whos elements have been mapped

through the supplied block
# File lib/sparsematrix/yale.rb, line 144
def collect(&block)
  return enum_for :collect unless block_given?
  clone.instance_eval { @elements.collect(&block) }
end
Also aliased as: map
column_count() click to toggle source

@return [Numeric] The number of columns in the matrix

# File lib/sparsematrix/yale.rb, line 151
def column_count
  row_index
  index_column.last + 1
end
Also aliased as: n
component(row, column)
Alias for: []
density() click to toggle source

@return the density of the SparseMatrix; that is, how many elements are

non-zero divided by the total size of the matrix
# File lib/sparsematrix/yale.rb, line 159
def density
  nonzero_element_count / (row_count * column_count * 1.0)
end
Also aliased as: sparsity
each(zeroes = false) { |self| ... } click to toggle source

Passes each element of the matrix to the supplied block @param block @return [YaleSparseMatrix]

# 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) { |element, row, column| ... } click to toggle source

Passes each element of the matrix and its index to the supplied block @param block @return [YaleSparseMatrix]

# 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
element(row, column)
Alias for: []
empty?() click to toggle source

Returns true if the matrix is empty; i.e. if {nonzero_element_count} is 0 @return [Boolean]

# File lib/sparsematrix/yale.rb, line 205
def empty?
  nonzero_element_count == 0
end
Also aliased as: zero?
include?(element) click to toggle source

Returns true if the matrix includes element @param element @return [Boolean]

# File lib/sparsematrix/yale.rb, line 213
def include?(element)
  @elements.include? element
end
index(element) click to toggle source

Returns the index of element in the matrix, or nil @param element @return [Array(Numeric, Numeric), nil]

# 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) click to toggle source
# 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
m()
Alias for: row_count
map(&block)
Alias for: collect
n()
Alias for: column_count
nnz()
nonzero_element_count() click to toggle source

The number of non-zero elements in the matrix @return [Numeric]

# File lib/sparsematrix/yale.rb, line 238
def nonzero_element_count
  @row_index.last
end
Also aliased as: nnz
row_count() click to toggle source

The number of rows in the matrix @return [Numeric]

# File lib/sparsematrix/yale.rb, line 245
def row_count
  row_index.length - 1
end
Also aliased as: m
saving_memory?() click to toggle source

Returns true if the SparseMatrix uses less memory than a naive matrix @return [Boolean]

# File lib/sparsematrix/yale.rb, line 252
def saving_memory?
  nnz < (m * (n - 1) - 1) / 2
end
sparsity()
Alias for: density
zero?()
Alias for: empty?

Private Instance Methods

add_row(count = 1) click to toggle source

Extends #{@row_index} @param count [Numeric] the number of rows to add

# File lib/sparsematrix/yale.rb, line 260
def add_row(count = 1)
  @row_index += [row_index.last] * count
end
Also aliased as: add_rows
add_rows(count = 1)
Alias for: add_row
element_index(row, column) click to toggle source

Calculates the index in {@elements} of the given matrix index. Returns nil if the index is outside the matrix's bounds. @param row [Numeric] @param column [Numeric] @return [Numeric, nil]

# File lib/sparsematrix/yale.rb, line 270
def element_index(row, column)
  index = row_start = row_index[row]
  row_end = row_index[row + 1]
  return nil unless row_start && row_end
  return nil if row_start == row_end
  while index < row_end
    current_column = index_column[index]
    return index if current_column == column
    if current_column > column
      return nil
    end
    index += 1
  end
  nil
end
nonzero_element_count=(nnz) click to toggle source

Sets the number of non-zero elements. For reasons, this is stored as the last element in {@row_index}. @param nnz [Numeric]

# File lib/sparsematrix/yale.rb, line 289
def nonzero_element_count=(nnz)
  @row_index[-1] = nnz
end