All (Notes) About Matrix (in Ruby)

Basis

New a matrix:

1
2
3
4
5
6
Matrix[[1,2], [3,4]]
Matrix.rows arr, copy=true
Matrix.columns arr
Matrix.build 3, 4 do |i, j|
...
end

New a special matrix:

1
2
3
4
Matrix.I
Matrix.zero
Matrix.scalar 5 #=> eq. to Matrix.I * 5
Matrix.diagonal 1, 2, 3, 4

Extract a sub matrix:

1
m.minor 0..2, 1..-1

Get rows/cols:

1
2
m.row_vectors
m.column_vectors

Get a row/col/elem:

1
2
3
m.row 2
m.column 2
m[2,2]

Basic Operations

1
2
3
4
m.det # determinant
m.inv # inverse
m.t # transpose
m.tr # trace, sum of diagonal elems

Four arithmetic operations +, -, * and / also work for vectors and numbers.

Row rank is the dimension of row vectors and column rank is the dimension of column vectors It is proved that row rank equals to column rank for a rectangular matrix:

1
m.rank

For complex matrices:

1
m.real, m.imag == m.rect

The conjugate of a complex matrix:

1
m.conj

In the following sections, I denote the conjugate transpose of $M$ as $M^{*}$. In the Ruby sense:

1
m.conj.t

Attributes

A square matrix is a matrix that its row_size equals to column_size.

1
m.square?

A hermitian is a square matrix that equals to it's conjugate transpose.

1
m.hermitian?

A positive-definite (real) matrix is an n-dimension matrix $M$ s.t.

$\forall$ real n-dimension vector $z$, $z^{T} M z > 0 $.

A positive-definite hermitian is a n-dimension hermitian $M$ s.t.

$\forall$ complex n-dimension vector $z$, $z^{*} M z > 0 $.

To test triangular matrices:

1
2
3
m.upper_triangular?
m.lower_triangular?
# diagonal matrix is upper_triangular and lower_triangular

An orthogonal (real) matrix $M$ means $M M^T = I$:

1
m.orthogonal?

Similar to orthogonal, a unitary (complex) matrix $M$ implies $M M^{*} = I$.

1
m.unitary?

A square matrix is regular if invertible.

A square matrix that is not regular is called singular or degenerate.

1
2
m.regular? # == (m.det != 0)
m.singular? # == !m.regular?

A permutation matrix is a square binary matrix that has exactly one entry 1 in each row and each column, and $0$s elsewhere.

1
m.permutation?

NOTE: Many of the above attributes raise error if matrix not square.

Eigen System

Eigenvalue and eigenvector: $A v = \lambda v$ .

The eigen decomposition ($d$ is diagonal matrix of eigenvalues):

1
v, d, v_inv = m.eigensystem

For each eigenvalue, the corresponding vector in $v$ is the eigenvector.

Decompositions

  • $LU$ ($L$ower triangle - $U$pper triangle decomposition):

    $A = L U$, a variant of Gaussian Elimination

  • $LDU$ decomposition:

    $A = L D U$ , where $D$ is diagonal

  • $LUP$ ($LU$ decomposition with partial pivoting):

    $P A = L U$, where $P$ is a permutation matrix

1
l, u, p = m.lup_decomposition

* To solve a linear equation with $LUP$ decomposition:

1
2
# m * x = b
x = m.solve(b)
  • Cholesky decomposition:

    $A = L L^{*}$, it is twice as efficient as $LU$ decomposition, but limited to positive-definite hermitians.

  • $QR$ decomposition:

    $A = Q R$, where $Q$ is orthogonal and $R$ upper triangular.

* there are block $LU$ and block Cholesky decompositions to reduce complexity.

NArray

Vector and Matrix are implemented in pure ruby array, which is polymorphic thus slow.

NArray is the ruby interface for POD arrays, which can make a performance boost.

1
gem i narray

http://narray.rubyforge.org/SPEC.en

There are methods to mutate the NArray:

1
2
3
4
a.add! b
a.sbt! b
a.mul! b
a.div! b

Boost Matrix Operation Speed with AVX

AVX stands for Advanced Vector Extension of Intel's recent CPUs. To be more superior than SSE, you can operate on 256 bit data with 1 instruction, which can be long as 2 or 4 elements in a matrix vector.

Just a reference (from IDF 2011):

How To Optimize Your Software For Intel AVX (It's interesting to see that you build software for their instruction set instead of them build instruction set for your software).

An i5 CPU should have AVX 1.0. But one needs at least GCC4.6 to enable this optimization.

Sparse Matrix and Parallel Matrix and Mathematica

TODO

Comments