Dot-product operators and strides for linear algebra


#1

Hi,

I am looking for the suitability of ruby for numerical applications.
I am currently using MATLAB and Octave for this purpose (see
www.octave.org, www.mathworks.com).

For vectors and matrices a single “" or “/” operator is not
sufficient to implement the necessary matrix/vector arithmetic in a
convinient and consistent operator notation. In OOPS languages like C++
which support operator overloading, Matrix class libraries usually
resort to a mixed functional/operator notation and assign the matrix
product to the "
” and implement the dot-product by a function e.g as
dot(A, B).

Besides product and division operators for matrix/vector operations 

it is necessary to introduce a transpose and hermite operator which is
of no interest in scalar arithmetic. In MATLAB the transpose of a
matrix X is expressed as X.’ and the conjugate transpose is X’.

A simple and compact example of how this notation can be used is in 

computing the 2-norm of a vector:
x = 1:1:10 % Vector counting from 1 to 10
norm2 = sqrt( xx’ ) % use matrix multiplication to compute the
squared sum
norm2 = sqrt(sum(x .
x)) % use elementwise multiplication
norm2 = sqrt(sum(x .^ 2)) % square element by element

In standart programming languages with an OOPS library this might 

look like:
x = [1 2 3 4 … 10] ;
norm2 = sqrt( x*x.transpose()) ; // use matrix multiplication
norm2 = sqrt(sum(dot(x, x))) ; // use dot-product auxiliary
function

While for such a simple example, there is not so much difference in 

readability, but for real world examples, the matrix operator notation
makes the code more compact and readable. Conceptionally it lacks
consistency, if the maybe more often used dot-product is implemented as
function and the matrix product as operator.

My assumption is that is might be possible to extend ruby with
reasonable effort to add the additional “.*” “./” and “.^2” binary
operators and the transpose / conjugate transpose operators. For the
standard ruby this function would just do the same as their scalar
conterparts, however, when implementing a matrix class these additional
operators can become alive and be used to implement the elementwise dot
operations.

Aside from the operators a second concept is quite essential for a 

scripting matrix and vector class. This requires a new data-type to
express strides.
Suppose one wants to access only every second element of a vector or
reverse a vector, then usually this has to be done in a loop. Since
looping over elements is prohibitively expensive in a scripting
language, the preferred solution for doing such common indexing
operation is to use strides. For ruby, it would be possible to define a
stride class, which stores the index of the first, last and stepsize.
Reversing a vector might look like:

   vector x=stride(1, 3) // use a stride to construct a new vector 

from 1 to 3.
reverse_x = x( stride(3, 1, -1) )

More elegantly, if strides are natively supported by the scripting 

language, then the example could be implemented as

  x = 1:3 ;
  reverse_x = x(3:-1:1) ;

Has anybody implemented a patch to include dot-operators or index 

strides to ruby? Are there any plans / discussion to include
MATLAB/Octave-alike features in the future?

Regards,

よろしくおねがいします

Roderick Koehle

References:
 * http://en.wikipedia.org/wiki/Matlab
 * http://en.wikipedia.org/wiki/IDL_programming_language

#2

On Feb 16, 2006, at 5:59 PM, removed_email_address@domain.invalid wrote:

My assumption is that is might be possible to extend ruby with
reasonable effort to add the additional “.*” “./” and “.^2” binary
operators and the transpose / conjugate transpose operators. For
the standard ruby this function would just do the same as their
scalar conterparts, however, when implementing a matrix class
these additional operators can become alive and be used to
implement the elementwise dot operations.

That’s an especially poor choice of operator name :wink:

a * b == a.*(b)

You could add a method called ., but you couldn’t call it in the
normal manner, you’d have to say:
a.send(".
", b)
which I don’t think is what you were looking for. As for “strides”,
have you seen ranges?

0…9 # 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
1…10 # 1, 2, 3, 4, 5, 6, 7, 8, 9

As for having an alternative step, you can use #step,

1.step(10, 2) { |x| p x }
1
3
5
7
9

To turn a step into a range-like object (instead of a method) use an
enumerator:

require ‘enumerator’
zero_to_twentyfive_by_five = 0.to_enum(:step, 25, 5)

zero_to_twentyfive_by_five.each { |x| p x }
0
5
10
15
20
25

In 1.9 you don’t even need to use the to_enum, ie you could simply write

zero_to_twentyfive_by_five = 0.step(25,5)


#3

On Feb 17, 2006, at 3:37 AM, removed_email_address@domain.invalid
removed_email_address@domain.invalid wrote:

The steps method, constructs an array immediately, this is not
necessary for strides.

Not true, step does not construct an array.


#4
  1. Operator/Method Abiguity: Clearly, this is a problem. I don’t think
    “.*” or the like operators would hurt too much though. It would be
    necessary to forbid “class.*method” style of methods and therefore a
    major design issue.

  2. Ranges: This is a good suggestion, but how to extend it to possibly
    n-dimensional matrices?
    I am not an expert on the implementation of ranges, by I suspect that
    ranges are executed by the interpreter. Strides can be executed by the
    matrix library and implemented more efficiently in C. The steps method,
    constructs an array immediately, this is not necessary for strides. If
    a stride is used for indexing it is only necessary to hand over the
    start, step and end index. Only if a stride is assigned to a vector,
    then it is necessary to convert it to an array.

Regards,

Roderick

Logan C. removed_email_address@domain.invalid schrieb:
On Feb 16, 2006, at 5:59 PM, wrote:

My assumption is that is might be possible to extend ruby with
reasonable effort to add the additional “.*” “./” and “.^2” binary
operators and the transpose / conjugate transpose operators. For
the standard ruby this function would just do the same as their
scalar conterparts, however, when implementing a matrix class
these additional operators can become alive and be used to
implement the elementwise dot operations.

That’s an especially poor choice of operator name :wink:

a * b == a.*(b)

You could add a method called ., but you couldn’t call it in the
normal manner, you’d have to say:
a.send(".
", b)
which I don’t think is what you were looking for. As for “strides”,
have you seen ranges?

0…9 # 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
1…10 # 1, 2, 3, 4, 5, 6, 7, 8, 9

As for having an alternative step, you can use #step,

1.step(10, 2) { |x| p x }
1
3
5
7
9

To turn a step into a range-like object (instead of a method) use an
enumerator:

require ‘enumerator’
zero_to_twentyfive_by_five = 0.to_enum(:step, 25, 5)

zero_to_twentyfive_by_five.each { |x| p x }
0
5
10
15
20
25

In 1.9 you don’t even need to use the to_enum, ie you could simply write

zero_to_twentyfive_by_five = 0.step(25,5)


#5

I guess a lot depends on what your performance requirements are. Octave
interfaces to LAPACK and the BLAS for its core numerical operations,
whereas Ruby currently uses either interpreted Ruby code or the built-in
primitives implemented in C. If your LAPACK and BLAS are backed by the
Automatically Tuned Linear Algebra Subroutines (ATLAS) you can do
numerical linear algebra on decent-sized problems at near peak hardware
speeds.

From reading the Pickaxe book, it doesn’t look like it would be too
difficult to interface Ruby to LAPACK and the BLAS. There is also a
primitive Ruby package on RAA that interfaces with the R language math
library. I got the Ruby/Rmath package working a few weeks ago but had to
drop the project to get some paid work done :). If anybody on the list
wants to pick this up, let me know and I’ll get you going on it.

I don’t know enough Ruby to even begin to design a math library. I have
played with the combination of Matrix, Mathn, Rational and Complex and
for small problems, they work well. My guess is that they would be
hopelessly slow for larger problems. I personally use R for all of my
numerical work and have no plans to move to another language – R is
designed for that and has a collection of library packages that do 98
percent of what I need.

By the way, what platform are you on? A lot of the GPL magic for
numerical computation works best on Linux and Solaris and second-best on
Windows and Macs. I’m on Gentoo Linux and I’ve got the works – R,
Octave, LAPACK and BLAS, both with the Atlas high-speed linear algebra
backing, TeXmacs, LyX, (wx)Maxima, Axiom, Ruby, Rails, etc.

removed_email_address@domain.invalid wrote:

   norm2 = sqrt( x*x' ) % use matrix multiplication to compute the squared sum

My assumption is that is might be possible to extend ruby with reasonable effort to add the additional “.*” “./” and “.^2” binary operators and the transpose / conjugate transpose operators. For the standard ruby this function would just do the same as their scalar conterparts, however, when implementing a matrix class these additional operators can become alive and be used to implement the elementwise dot operations.
x = 1:3 ;
References:
* http://en.wikipedia.org/wiki/Matlab
* http://en.wikipedia.org/wiki/IDL_programming_language


Telefonieren Sie ohne weitere Kosten mit Ihren Freunden von PC zu PC!
Jetzt Yahoo! Messenger installieren!


M. Edward (Ed) Borasky

http://linuxcapacityplanning.com