Skip to content

cliffordwolf/NumJS

Repository files navigation

     Note: I am not actively maintaining this library anymore. (But I
    will accept pull requests.) If you are considering this library you
     should also consider writing your code in C/C++ and compile it to
             JavaScript with Emscripten. That's what I do now.

      - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * -


NumJS -- A JavaScript library for numerical computing
=====================================================


This library provides:

    - classes and functions for doing computations with
        * Real and Complex Numbers
        * Real and Complex Matrices
        * Permutation Matrices

    - linear decompositons and linear solvers:
        * LU and PLU decomposition
        * QR decomposition [TBD]
        * singular value decomposition [TBD]
        * linear least-squares fitter [TBD]

    - special functions:
        * B-spline basis functions [TBD]
        * Gauss error function [TBD]

    - polynomials:
        * evaluating polynomials [TBD]
        * numerical polynomial solver [TBD]

The items marked as [TBD] aren't implemented yet. Feel free to implement
them (and/or other stuff) and send me your pull requests.


A warning about numerical computing with JavaScript
---------------------------------------------------

Some JavaScript implementations store numbers as single precision (32bit)
floating point values. So the possible applications for JavaScript in the world
of numerical computing is in fact very limited and you should always make sure
that you understand how to estimate the numerical errors in the calculation you
want to perform.

Some of the more advanced routines in this library use the value NumJS.eps to
determine when a value is small enough to be treated as zero. The value of
NumJS.eps is initialized to the square root of the machine epsilon when NumJS
is loaded.


Real and Complex Numbers
------------------------

JavaScript does not support operator overloading. So in all arithmetric that
might involve objects other then real numbers must be performed via the
following NumJS function:

	NumJS.ADD(x, y)        .... x + y
	NumJS.SUB(x, y)        .... x - y
	NumJS.MUL(x, y)        .... x * y
	NumJS.DOT(x, y)        .... x . y
	NumJS.DIV(x, y)        .... x / y
	NumJS.SOLVE(x, y)      .... x \ y
	NumJS.POW(x, y)        .... x ^ y

	NumJS.INV(x)           .... 1/x
	NumJS.NEG(x)           .... -x
	NumJS.ABS(x)           .... abs(x)
	NumJS.NORM(x)          .... norm(x)  (euclidean norm)
	NumJS.ARG(x)           .... arg(x)
	NumJS.CONJ(x)          .... conjugate(x)
	NumJS.TRANSP(x)        .... transpose(x)
	NumJS.EXP(x)           .... e^x
	NumJS.LOG(x)           .... log(x)
	NumJS.DET(x)           .... det(x)
	NumJS.RE(x)            .... real_part(x)
	NumJS.IM(x)            .... imaginary_part(x)
	NumJS.ROUND(x, N)      .... round(x)  (to N decimals)

	NumJS.EQ(x, y)         .... x == y
	NumJS.EQ_ABS(x, y, T)  .... x == y  (with max abs error T)
	NumJS.EQ_REL(x, y, T)  .... x == y  (with max rel error T)

Note that not all objects support all operations. Whenever an operation
is performed on objects that do not support it, a "NumJS.* type error"
exception is thrown.

The script "opmap.html" generates a table showing the allowed operand
types for each operation.

For real numbers the native JavaScript number type is used:

	var x = 1.2345;

Complex numbers can be created using the NumJS.C(re, im) helper function:

	var z = NumJS.C(1, 1);

or in polar coordinates using the NumJS.P(abs, arg) helper function:

	var z = NumJS.P(Math.PI/4, Math.sqrt(2));

Complex numbers have a .toString() method that is automatically used by
the interpreter to convert a complex number to a string when needed. They
also have .toFixed() and a .toPrecision() methods that are compatible with
the generic JavaScript .toFixed() and .toPrecision() number methods.


Expression Parser
-----------------

It can be hard to write complex expressions using the NumJS.* operator functions.
So NumJS comes with en expression parser for infix expressions that can be used
to automatically create functions that use the NumJS.* operators from string
expressions:

        var func = eval(NumJS.Parse(
			"a + b * -(c / pow(-2i, a)) + b",
			"a, b, c", { pow: "NumJS.POW" }));
	var result = func(1, 2, 3);

The 1st argument to NumJS.Parse() is the expression to generate a function for.
The 2nd argument to NumJS.Parse() is the argument list for the generated function
and the 3rd argument is a hash with all local defines (like short forms for
function calls) to be included in the generated function. The JavaScript code
that is returned by NumJS.Parse() looks like this:

	(function(a, b, c){
		var pow = NumJS.POW;
		var $0 = NumJS.C(0, 2);
		var $1 = NumJS.NEG($0);
		var $2 = pow($1, a);
		var $3 = NumJS.DIV(c, $2);
		var $4 = NumJS.NEG($3);
		var $5 = NumJS.MUL(b, $4);
		var $6 = NumJS.ADD(a, $5);
		var $7 = NumJS.ADD($6, b);
		return $7;
	})

The parser accepts the following constructs in expressions:

	- number literals and variable names
	- imagenary literals (a number followed by 'i')
	- matrices using [ a, b, c; d, e, f ] notation
	- ( .. ) blocks and function calls
	- prefix '+' (ignored) and '-' (NumJS.NEG)
	- infix '*' (NumJS.MUL)
	- infix '/' (NumJS.DIV)
	- infix '\' (NumJS.SOLVE)
	- infix '+' (NumJS.ADD)
	- infix '-' (NumJS.SUB)

It is generally recommended to parse and evaluate an expression only once and
then reuse the resulting function handler for subsequent calculations.


Matrices
--------

Matrices can be created using one of the following two functions:

	var matrix3x3 = NumJS.MAT(3, 3);
	var permut3x3 = NumJS.PMAT(3);

Normal matrices are initialized to all-zeros and can be filled using the
.set(row, col, value) method. Note that row and column indexes start with 0.

Permutation matrices are initialized to the identity matrix and can be
modified using the .pivot_col(c1, c2) and .pivot_row(r1, r2) methods,
that pivot the two specified rows or columns.

Alternatively matrices can be initialized using their constructors by passing
and additional array with the initialization data in row-major order:

	var matrixFlip3x3 = NumJS.MAT(3, 3, [
		0, 0, 1,
		0, 1, 0,
		1, 0, 0
	]);

Permutation matrices can also be created with initalization data. In this
case the array must contain the row-number of each '1' per column:

	var permutFlip3x3 = NumJS.PMAT(3, [2, 1, 0]);

There is no special vector class. So vectors must simply be created as
Nx1 matrices.

Matrix-matrix and matrix-scalar operations can be performed using the
uppercase NumJS.* metioned above and work as one would expect it. E.g.:

	var A = NumJS.MAT(2, 2, [1, 2, 3, 4]);

	var B_re = NumJS.MAT(2, 2, [5, 6, 7, 8]);
	var B_im = NumJS.MAT(2, 2, [9, 0, 1, 2]);
	var B = NumJS.ADD(B_re, NumJS.MUL(B_im, NumJS.C(0,1)));

	var Z = NumJS.MUL(A, B);

Individal matrix elements can be accessed using the .get(row, col) method.

Note that also permutation matrices provide a .get(row, col) method, but
lack support of a .set(row, col, value) method.

A copy of a matrix can be created using the .copy() method. This method
converts permutation matrices into normal matrices. If this is not the desired
behavior, use the .clone() method instead.

A row-major array of matrix block can be generated using the matrix
.cut(row, col, nRows, nCols) method. A block of a matrix can be written
using the matrix .paste(row, col, nRows, nCols) mehthod. The methods
.cut_cm() and .paste_cm() do the same for column-major arrays. This
functions can be used to easily rearange matrices or initialize them
row- or column-wise:

	var A = NumJS.MAT(3, 3);
	A.paste(0, 0, 1, 3, [ 1, 2, 3 ]);
	A.paste(1, 0, 1, 3, [ 4, 5, 6 ]);
	A.paste(2, 0, 1, 3, [ 7, 8, 9 ]);

The dimension of a matrix is stored in its .rows and .cols properties.
A permutation matrix has an additional .sign property that holds the
sign of the permutation.

Matrices also have a .toString() method that is automatically used by the
interpreter to convert a Matrix to a string when needed. They also have
.toFixed() and a .toPrecision() methods that are compatible with the generic
JavaScript .toFixed() and .toPrecision() number methods.

Additionally matrices also have a .toTextBlock() method that creates
a nice multi-line text representation of the matrix.


Reduced row echelon form of a matrix and matrix rank
----------------------------------------------------

Each matrix object provides the method .rref() that calculates the
reduced row echelon form of the matrix. The matrix object returned
by .rref() has an additional property .pivcols that is an array with
the indices of all pivot columns.

The number of elements in .rref().pivcols is also the rank of the
matrix. For convinience each matrix object also has a .rank() method
that simply returns the value of .rref().pivcols.length.


PA = LU factorization and solver
--------------------------------

Each matrix object provides the methods .LU() and .PLU() that perform
an LU factorization and return a PLU object when the factorization was
successful and null if the matrix can't be factorized.

The result of a factorization is cached. So successive callc to .LU()
or .PLU() do not introduce any significant performance problem.

The .LU() method performs LU factorization without pivoting and .PLU()
performs factorization with pivoting. In most cases factorization with
pivoting is prefered over factorization without pivoting.

The PLU object stores the factorization in the properties .P, .L and .U
with .P beeing a permutation matrix object and .L and .U beeing normal
matrices.

Per definition .L is a lower triangular matrix with all ones on the main
diagonal and .U is an upper triangular matrix.

The PLU.solve(Y) method solves a linear system using the factorization:

	// solve A*X = Y for X:
	var A = NumJS.MAT(n, n, [ ... ]);
	var Y = NumJS.MAT(n, k, [ ... ]);
	var X = A.PLU().solve(Y);

This is actually identical to using the NumJS.SOLVE() operator:

	// solve A*X = Y for X:
	var X = NumJS.SOLVE(A, Y);

The PLU.det() method calculates the matrix determinant using the
factorization (product along the diagonal of U times sign of P). The
NumJS.DET(M) operator is using PLU.det() behind the scenes to
calculate a matrix determinant.

About

NumJS -- A JavaScript library for numerical computing

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published