matrices in Haskell 
Author Message
 matrices in Haskell

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  
 matrices in Haskell

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
behaviour for free.

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  
 matrices in Haskell

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
> behaviour for free.

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  
 matrices in Haskell

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  
 
 [ 4 post ] 

 Relevant Pages 

1. Matrix operations in Haskell

2. Matrix Multiplication: 2 n x n matrices

3. Complex Matrix => Inverese Matrix

4. Haskell, Miranda to Haskell

5. ANNOUNCE: Glasgow Haskell 2.01 release (for Haskell 1.3) [repost]

6. ANNOUNCE: Glasgow Haskell 0.29 release (for Haskell 1.2) [repost]

7. ANNOUNCE: Glasgow Haskell 0.29 release (for Haskell 1.2)

8. How to turn nest of matrices into one matrix?

9. Matrix op speaks. Computer programmers needed to build matrix.

10. Matrix op speaks. Computer programmers needed to build matrix.

11. Matrix op speaks. Computer programmers needed to build matrix.

12. Matrix op speaks. Computer programmers needed to build matrix.

 

 
Powered by phpBB® Forum Software