Author Message

Hello everybody,

I am trying to write some simple numerical programs in Haskell,
and therefore I am badly in need of a library with matrix functions.
I looked around on the net, but I couldn't find any existing library.

Perhaps somebody can help me out?

In the mean time, I have written my own Matrix type with some basic
operations on it. It is usable, although I would like a more
powerful alternative if it is easily available...

My current implementation uses lists, but perhaps I should use arrays.
Can somebody give me an impression of the speed benefit of arrays
compared to lists?
Perhaps it's worth the trouble to reimplement my matrix stuff.

Thanks a lot,

Stephan

--
S.H.M.J. Houben

Philips Research Laboratories
Building WAY, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands
Phone: +31-40-2744789

Mon, 05 Feb 2001 03:00:00 GMT

Quote:

> My current implementation uses lists, but perhaps I should use arrays.

You could also consider quadtrees, think of each matrix as four
quadrants, each also being a matrix or a scalar value (or, for
performance, an n by n array)

(Or, if you need arbitrarily dimensioned matrices, not just powers of
two, you could divide each dimension into some prime number, and get a
more arbitray, but messy, implementation.)

Using trees makes a lot of operations neatly recursive, and probably
gives you the benefit of cheap sparse matrices as well as good cache

Quote:
> Can somebody give me an impression of the speed benefit of arrays
> compared to lists?

I would say this is an implementation issue, but I expect arrays to be
faster.

Quote:
> Perhaps it's worth the trouble to reimplement my matrix stuff.

Perhaps.  I'd be very interested in any code you produce.  Stray
thought: matrices are usually linear functions on vectors, the
rectangular bunch of numbers is just the representation.  I think one
should be able to type something like

x' = b - D' (L + U) x
where
(L,D,U) = split A
D' = inv D

kzm
--
If I haven't seen further, it is by standing in the footprints of giants

Tue, 06 Feb 2001 03:00:00 GMT

Quote:

> You could also consider quadtrees, think of each matrix as four
> quadrants, each also being a matrix or a scalar value (or, for
> performance, an n by n array)

<snip>

Quote:
> Using trees makes a lot of operations neatly recursive, and probably
> gives you the benefit of cheap sparse matrices as well as good cache

Good idea. Perhaps I'll steal it ;-)

Quote:
> > Perhaps it's worth the trouble to reimplement my matrix stuff.

> Perhaps.  I'd be very interested in any code you produce.

You can get my list-based stuff at:

http://www.win.tue.nl/math/an/stephanh/Matrix.hs

I implemented QR-decomposition instead of (P)LU-decomposition,
because itcan also be used to solve least-square-problems.

So although it is less efficient, it gives you more functionality
in less time. Which is not a bad idea for a first prototype ;-)

Quote:
> Stray
> thought: matrices are usually linear functions on vectors, the
> rectangular bunch of numbers is just the representation.  I think one
> should be able to type something like

>         x' = b - D' (L + U) x
>                 where
>                         (L,D,U) = split A
>                         D' = inv D

But to do that, you need to overload function-application.
Which is not possible in Haskell, I believe.

My list-based implementation is fairly complete now.
One of the things it does *not* do is to check whether matrix dimensions
are compatible. Which they better be, since otherwise the results make
no sense. Perhaps I should perform run-time checks, but on the
other hand -- that would make matrix operations even more expensive.

Greetings,

Stephan

--
S.H.M.J. Houben

Philips Research Laboratories
Building WAY, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands
Phone: +31-40-2744789

Tue, 06 Feb 2001 03:00:00 GMT

Quote:

> Perhaps it's worth the trouble to reimplement my matrix stuff.

Just in case this helps, there are two papers on sparse matrix
implementation in:

Robert L. Wainwright and Marian E. Sexton. A study of sparse matrix
representations for solving linear systems in a functional language.
Journal of Functional Programming, 2(1):61-72, January 1992

P.W. Grant, J.A. Sharp, M.F. Webster and X. Zhang. Sparse matrix
representations in a functional language - Journal of Functional
Programming, 6(1):143-170, January 1996.
Abstract at:
http://www.dcs.glasgow.ac.uk/jfp/bibliography/References/grantswz1996...

Graeme.

Sun, 11 Feb 2001 03:00:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages