
Data Structures for Linear Algegra / reply to another forum
I have posted this reply to a message in the forum
sci.math.num-analysis
Bill Knight/ University of New Brunswick / Canada
====================================================================
Quote:
>Hi,
>I am working on a project for Lin. Algebra and wanted to get some
>suggestions on how to define structures for Linear Algebra.
.---------------------------------------------------------------.
| How about working in APL wherein the structures are already |
| present? |
'---------------------------------------------------------------'
Quote:
>The idea is to make the basic operations (+, -, transpose, row/column
>shifts etc) as efficient and simple as possible. Then develop other
.---------------------------------------------------------------.
| Already built into APL are, |
| +, -, transpose, row/column shifts, submatrices, |
| catenation, matrix product, Hadamard product, etc. |
| The notation is fairly close to normal mathematical notation |
| and more succinct and tidy than any notation we are likley |
| to invent for ourselves. |
| |
| Example 1: |
| t -1 |
| C := A (B + C) A |
| translates to APL word for word. |
| C <- (transpose A) +.x (inverse (B + C)) +.x A |
| [ +.x stands for "sum of products" which is exactly what a |
| matrix multiplication is.] |
| A
fortran implementation needs 5 subroutine calls, looks |
| nothing like the original expression, and is generally ugly. |
| |
| Example 2: |
| The leading 3 by 3 submatrix of matrix A is |
| A[1 2 3 ; 1 2 3] |
| |
| Example 3: |
| The Strassen algorithm which multiplies matrices in time |
| O( N power 2.807.. ), |
| a traditional bear in traditional languages, is a snap in APL.|
| You can copy the equations, almost as they are written in |
| Strassen's paper, into your program. |
| |
'---------------------------------------------------------------'
Quote:
>matrix functions based on these ....
>A naive solution would be define a matrix struct:
> struct matrix{
> int rows;
> int cols;
> double **data;
> }
>and treat all vectors as being of one column matrices. Are there better
>ways of doing this? Any ideas?
.---------------------------------------------------------------.
| Of course this approach leaves you with transpose operations |
| scattered throughout your expressions which are the more |
| annoying since the transpositions are actually irrelevant. |
| (A quirk of APL notation avoids irrelevant transpose marks.) |
'---------------------------------------------------------------'
Quote:
>What i will be wanting to do next is to implement multiple precision data
>types ......
.---------------------------------------------------------------.
| See -- |
| Robert G. Willhoft 1992 |
| Matrix Operations Over Integral Domains Using Nested Arrays |
| in the Conference Procedings of the International Conference|
| on APL, 6-10 July 1992, St. Petersburg (Leningrad), |
| Russia. pages 275-285 |
'---------------------------------------------------------------'
Quote:
Bill Knight / University of New Brunswick / Canada