scijs / ndarray-blas-level1 Goto Github PK

BLAS Level 1 operations for ndarrays

License: MIT License

JavaScript 100.00%

ndarray-blas-level1's Introduction

ndarray-blas-level1

A quick note on why this exists: The goal is not to reinvent the wheel. There are lots of implementations of BLAS out there. Even for JS. There's a nodejs wrapper for LAPACK. Depending on what you need, maybe you should use that. The goal of this is to bring standardized BLAS operations to ndarrays so that algorithms can be made as future-resistant as possible by writing them in terms of standardized, easily-translatable operations.

Usage

This library implements the basic vector operations of the Level 1 Basic Linear Algebra Subprograms (BLAS). Many of these functions are also implemented in ndarray-ops—which also has functions that are not included in BLAS. So the right answer is probably some blend of the two. This library exists mainly to frame things in a relatively standard, coherent framework.

NB: This library performs no checks to ensure you're only passing one-dimensional vectors. It simply iterates across the first dimension of the array, so if you pass it higher-dimensional arrays, don't expect a meaningful result.

Function	Operation	Description
`swap(x,y)`	$x \leftrightarrow y$	Swap the elements of x and y
`scal(alpha,x)`	$x \leftarrow \alpha x$	Multiple vector x by scalar alpha
`copy(x,y)`	$y \leftarrow x$	Copy x into y
`axpy(alpha, x, y)`	$y \leftarrow \alpha x + y$	Multiple x by alpha and add it to y
`cpsc(alpha, x, y)`	$y \leftarrow \alpha x$	Multiply x by alpha and assign it to y
`dot(x,y)`	$dot \leftarrow x^T y$	Calculate the inner product of x and y.
`nrm2(x)`	$nrm2 \leftarrow \|\|x\|\|_2$	Calculate the 2-norm of x
`asum(x)`	$asum \leftarrow \|\|x\|\|_1$	Calculate the 1-norm of x
`iamax(x)`	$\underset{i} {\mathrm{argmax}} \|x_i\|$	the argmax of x
`rotg(a,b)`		Calculates the Givens rotation parameters [c, s, r]

Example

Usage should be pretty straightforward. There aren't really any options or variations.

var blas1 = require('ndarray-blas-level1');

var x = ndarray([1,2,3]);
var y = ndarray([3,4,5]);

blas1.axpy(2, x, y);

License

Authors

Ricky Reusser, Philipp Burckhardt, Tim Bright

ndarray-blas-level1's People

Contributors

Stargazers

Watchers

Forkers

tab58

ndarray-blas-level1's Issues

Make work for regular and generic ndarrays

ndarray-proxy arrays behave differently than regular ndarrays powered by an Array or TypedArray. They have a getter/setter. This library must work with both. The difference is simple to implement, but doing it efficiently either requires enumeration of all possible cases which is unrealistic or is requires dynamic code generation and is tantamount to an ad-hoc rewrite of cwise, which is silly. I don't yet know the correct solution.

Use cwise as a transform

This is awesome! One suggestion though is that you should consider adding cwise as a browserify transform. That way when you ship out bundles it will generate less code overall, saving the esprima dependency.

To do this, all you have to do is add the following field to your package.json:

  "browserify": {
    "transform": [
      "cwise"
    ]
  }

Split into files

Doing these correctly (handling generic matrices, simplifications, type-checking, etc.) requires enough work that this should probably be split into individual repos.

Check for simplifications

Mostly just checking to see if complicated calls reduce to a simpler ones. (e.g. alpha = 0 yields obvious simplifications)

See: http://www.netlib.org/atlas/developer/atlas_contrib/node44.html

Polyfills

Implementing the Givens rotation function rotg required a Math.sign() function which isn't present in older Node versions such as v0.10. I don't necessarily like having a polyfill, but maybe others can suggest a better option.

Add complex support.

I think the sensible option is to prefix the operations with a 'c' in the style of BLAS. Not sure there's actually much logic to rewriting BLAS here other than the fact that it's pretty standard.

Replace cwise with explicit loops

cwise makes sense for ndarray-ops or perhaps for very large vectors, but it's totally the wrong tool for 1D vectors and severely slows things down by about a factor of 100.

Kahan Summation

For the extra added numerical accuracy kick, would it be appropriate to write a Kahan summation algorithm and use it for functions like dot(), nrm2(), and asum() seeing as how they're basically sums anyway?

I guess the real question here is whether the overhead is worth the extra bit of accuracy. I know I would be interested in getting the accuracy for my own projects, but maybe it's not everyone's focus.

Prevent overflow in nrm2

Nrm2 is a meaningful function for lots of algorithms, but it's not great since the naive implementation square roots the valid floating point range. A floating point aware version normalizes by the max entry, normalizes by the length of the input, and perhaps even orders additions by magnitude of the elements, although that last one seems like too much. This makes it a two step process. Find the magnitude of the input, then add with normalization and rescale the output. Maybe there should be a safe version with optional scale that otherwise falls back to checking the size if not provided. Not the end of the world, but I'd like to keep the algorithms optimized and robust. Perhaps this is best handled by avoiding nrm2 in the first place, when possible. Netlib notes that this function was not added for the sake of optimization.

See: http://www.netlib.org/atlas/developer/atlas_contrib/node60.html

Node v4.0 and Beyond

I was wondering why Travis doesn't run checks on Node.js beyond v0.12. The primary push for wanting more advanced versions that was more my use of the Math.sign function, which was AFAIK introduced in ES2015. I had to polyfill it in for Travis to run correctly.

I'm not sure this is a real issue since the rest of the code is obviously compatible with practically all versions of Node, but I thought I'd bring it up.

Oops. Images ended up in wrong directory.

Needs cleanup.

Implement iamax (argmax)

Didn't happen to know how to get the index inside the cwise body, but looks like you're already on it, @Planeshifter! Thanks!!! Makes my day. Probably needs a quick test, but otherwise you can go ahead and pull-request/merge if/when you feel good about it.

Style Guide

I'm raising this issue because of my love for semicolons (can we really rely on semicolon insertion?). I'm fine if that's the style, but I think there ought to be a style guide for future collaboration.

Feel free to push back on this.