Chris Umbel

The Sylvester Matrix Library Comes to Node.js

Before some recent machine learning implementations in node I set out to find a reasonable matrix math/linear algebra library for node.js. The pickings were slim but I managed to dig up a general JavaScript matrix math library written by James Coglan called sylvester. Clearly, sylvester had to be node-ified.

With the help of Rob Ellis (a collaborator on natural) it's been wrapped up into a node project titled node-sylvester & NPM and has had some features added such as element-wise multiplication, QR, LU, SVD decompositions and basic solving of systems of linear equations.

In this post I'll cover some of the basic structures and operations supported by sylvester, but it will by no means be complete. I'll focus solely on the Matrix and Vector prototypes, but sylvester also supports Line, Plane, and Polygon. Also within the covered prototypes I'll only demonstrate a small, but useful subset of their functionality.

Currently, the only reasonable sources of documentation for functionality existing only in the node port are in the README while general sylvester functionality is covered in its API docs. In time I will (hopefully with the help of the community) provide some more complete documentation.

Installation

Getting ready to use the node port of sylvester is what you'd expect, a standard NPM install.

npm install sylvester

You can then require-up sylvester in your node code and use the prototypes within.

var sylvester = require('sylvester'),
  Matrix = sylvester.Matrix,
  Vector = sylvester.Vector;

Vector and Matrix Prototypes

Matrices and vectors are abstracted by the Matrix and Vector prototypes.

Instances can be created using their create functions and passing in an array of values. Vector.create accepts a one dimensional array of numbers and Matrix.create accepts multiple dimensions.

var x = Vector.create([1, 2, 3]);
var a = Matrix.create([[1, 2], [3, 4]]);

representing:

Global shortcuts exist to clone Vector and Matrix prototypes with $V and $M respectively. The following is the semantic equivalent of the previous example.

var x = $V([1, 2, 3]);
var a = $M([[1, 2], [3, 4]]);

Matrix's Ones function will create a matrix of specified dimensions with all elements set to 1.

var ones = Matrix.Ones(3, 2);

Matrix's Zeros function does the same except with all elements set to 0.

var zeros = Matrix.Zeros(3, 2);

An identity matrix of a given size can be created with Matrix's I function.

var eye = Matrix.I(4);

Data Access

Values can be retrieved from within a Matrix or Vector using the e method.

a.e(2, 1); // returns 3
x.e(3); // returns 3

The entire set of values can be retrieved/manipulated with the elements member of Matrix and Vector. elements is an array-of-arrays-of-numbers in the case of matrices and it is a simple array-of-numbers for vectors.

var a_elements = a.elements; // [[1, 2], [3, 4]]
var x_elements = x.elements; // [1, 2, 3]

Basic Math

Many standard mathematic operations are supported in Vector and Matrix clones. In general the arguments can either be scalar values or properly-dimensioned Matrix/Vector clones. While not covered here element-wise versions of many multiplicative/specialized operations are also available.

Matrices and vectors can be added-to and subtracted-from by scalar values using the add and subtract functions.

var b = a.add(1);
var d = a.subtract(1);

symbolizing:

Naturally, like-dimensioned matrices and vectors can be added to and subtracted from each other.

var e = a.add($M([[2, 3], [4, 5]]));
var f = a.subtract($M([[0, 2], [3, 3]]));

meaning:

Matrices/vectors can be multiplied with matrices/vectors of appropriate dimensions.

var g = a.x($V([3, 4]));

The dot-product of two vectors can be computed with Vector's dot method.

var y = x.dot($V([4, 5, 6]));

depicting:

Transposing

A Matrix can be transposed with the transpose method.

var at = a.transpose();

where at represents the matrix:

Segmentation/Augmentation

The first n elements can be removed from a Vector with the chomp method.

var n = 2;
var xa = x.chomp(n);

In contrast the first n elements can be retrieved with the top method.

var xb = x.top(n);

Vectors can have a list of values appended to the end with the augment method.

var xc = x.augment([4, 5]);

Matrices can have a column appended to the right with Matrix's augment method.

var m = a.augment($V([3, 5]));

A sub-block of a Matrix clone can be retrieved with the slice method. slice accepts a starting row, ending row, starting column and ending column as parameters.

var aa = $M([[1, 2, 3], [4, 5, 6], [7, 8, 9]]);
var ab = aa.slice(1, 2, 1, 2);

The code above produces a matrix ab shaped like:

Decompositions/Advanced functions

A small number of decompositions are currently supported. These have all been recently added and at the time of writing are, while functional, not necessarily as computationally efficient as they could be. Also their stability cannot be guaranteed at this time.

Note that these were all implemented in pure JavaScript. My personal hope is to keep node-sylvester 100% functional in pure JavaScript to maintain the best compatibility across all platforms. In the long run, however, I hope to employ time-tested, computationally-efficient native libraries to perform these operations if the host machine allows.

A QR decomposition is made possible via Matrix's qr method. An object is returned containing both the Q and the R matrix.

var qr = a.qr();

resulting in the object:

{ Q: 
   [-0.316227766016838, -0.9486832980505138]
   [-0.9486832980505138, 0.3162277660168381],
  R: 
   [-3.162277660168379, -4.427188724235731]
   [5.551115123125783e-16, -0.6324555320336751] }

Singular Value Decompositions (SVD) can be produced via Matrix's aptly named svd method. An object is returned containing the U (left singular), S (singular diagonal), and V (right singular) matrices.

var svd = a.svd();

which returns:

{ U: 
   [0.40455358483359943, 0.9145142956773742]
   [0.9145142956773744, -0.40455358483359943],
  S: 
   [5.4649857042190435, 0]
   [0, 0.36596619062625785],
  V: 
   [0.5760484367663301, -0.8174155604703566]
   [0.8174155604703568, 0.5760484367663302] }

Principal Component Analysis can be performed (dimensionality reduced) and reversed (dimensionality restored with approximated values) using Matrix's pcaProject and pcaRecover methods respectively.

pcaProject accepts the number of target dimensions as a parameter and returns an object with the reduced data Z and the covariant eigenvectors U.

var pca = a.pcaProject(1);
{ Z: 
   [2.2108795577070475]
   [4.997807552180416],
  U: 
   [0.5760484367663208, -0.8174155604703633]
   [0.8174155604703633, 0.5760484367663208] }

and pcaRecover approximately recovers the data to the original dimensionality.

pca.Z.pcaRecover(pca.U);   

which produces:

Solving Linear Equations

Simple linear equations in the form of

can be solved using the suitability-named solve method.

var A = $M([
    [2, 4],
    [2, 3],
]);

var b = $V([2, 2]);
var x= M.solve(b);

which is representative of

Conclusion

Thanks to James Coglan's hard work on sylvester plenty of matrix math functionality has been exposed to JavaScript. With a little extra work we've been able to expose quite a bit more to node. There's still more work to do not only in optimization but also in capabilities. In time hopefully node-sylvester will become fast and complete.

As a reminder, the functionality outlined above is not representative of the full list of current capabilities. Between the README in the source and the sylvester API documentation you should be able to get a reasonably clear picture. Still, if you're looking for ways to help with the project a concerted documentation effort would be wonderful and appreciated.

Sat Dec 17 2011 05:00:00 GMT+0000 (UTC)

Follow Chris
RSS Feed
Twitter
Facebook
CodePlex
github
LinkedIn
Google