Inversion
Author Message
Inversion

Anybody know how to invert a matrix ?
I have no idea how to write an algorihm like that since I barely even know
matrix, so any help, if possible the whole program, would be appreciated.

Thanks
--

Sat, 05 Apr 2003 03:00:00 GMT
Inversion

Quote:
> Anybody know how to invert a matrix ?
> I have no idea how to write an algorihm like that since I barely
> even know matrix, so any help, if possible the whole program,
> would be appreciated.

Get Sedgewick's book "Algorithms in C", or his earlier clearer
"Algorithms" (in Pascal).

The simple method is O(N2) Gaussian reduction, but much faster and
more complicated methods exist.

--

http://www.qwikpages.com/backstreets/cbfalconer/
--

Sat, 05 Apr 2003 03:00:00 GMT
Inversion

Quote:

> Anybody know how to invert a matrix ?
> I have no idea how to write an algorihm like that since I barely even know
> matrix, so any help, if possible the whole program, would be appreciated.

I wonder what brought to your mind the idea that this would be a
question about C programming... As is, this strictly a mathematical or
maybe algorithmical question, still. It may become a C programming
question, later on, but that point is not reached, yet.

A simple Web search with keywords like 'matrix inversion' and 'C'
should get you what you want. Note that there are *lots* of methods,
for lots of special cases, and just looking at existing code will most
matrix inversion in particular. I strongly suggest you get your nose
stuck in a maths textbook, first...
--

Even if all the snow were burnt, ashes would remain.
--

Sat, 05 Apr 2003 03:00:00 GMT
Inversion

Quote:
>Anybody know how to invert a matrix ?
>I have no idea how to write an algorihm like that since I barely even know
>matrix, so any help, if possible the whole program, would be appreciated.

If you know so little why do you want to do it? Homework? Well most of
us are too kind to sabotage your learning by short-cutting it.

Francis Glassborow      Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
--

Sat, 05 Apr 2003 03:00:00 GMT
Inversion

Quote:

> Anybody know how to invert a matrix ?
> I have no idea how to write an algorihm like that since I barely even know
> matrix, so any help, if possible the whole program, would be appreciated.

The best way to do this is not to do it at all. Inverting
a matrix isn't hard, but doing a good job of it can be;
there are situations where the simple algorithms that
work well in theory perform poorly in practice, mostly
due to the merely finite precision you have to work with.

There are a number of very powerful and well-tested libraries
that will do what you need; you'd probably do best to pick
up LAPACK, a set of fortran77 libraries, or CLAPACK, its C
translation. Both are available from netlib, http://www.netlib.org.

--
Mark Jeffcoat
--

Sat, 05 Apr 2003 03:00:00 GMT
Inversion

Quote:

>> Anybody know how to invert a matrix ?
>> I have no idea how to write an algorihm like that since I barely
>> even know matrix, so any help, if possible the whole program,
>> would be appreciated.

>Get Sedgewick's book "Algorithms in C", or his earlier clearer
>"Algorithms" (in Pascal).

>The simple method is O(N2) Gaussian reduction, but much faster and
>more complicated methods exist.

Err, not quite.

1. Books.

The _only_ good book I have ever seen on C code for numerical analysis
is the book "Numerical Recipes in C".

2. Gaussian elimination.

No competent numerical analyst would use it as such, however it is the
basic idea behind the LU decomposition.  Both algorithms have exactly
the same complesity, namely O(n^3) for solving systems of linear
equations.  To invert a matrix, there are n systems of linear equations,
so that's O(n^4) in all.  There are also slower but more stable methods.

3. Never invert a matrix.

There are exceptions, but not many.  The reason is simply that it is too
expensive in CPU time.  Almost always, explicit inverses in formulae
involve matrix-vector multiplications like A^{-1}b, which can be
computed by solving Ax=b.  This is now a O(n^3) operation.  (I should
perhaps add that serious numerical problems are all compute bound, so
program efficiency is always a prime consideration.)

4.  Complexity

Yes, there are faster ways of inverting matrices, but we almost never
want to invert them.  Strassen's algorithm is faster, complicated to
program, and very numerically unstable.  This renders this algorithm as
unusable.  Algorithms that are faster than the LU decomposition remain
theoretical curiosities only.

Cheers,
Mike

--

address.  It is a mail alias.  Once spammed, the alias is deleted, and
the integer 'N' incremented.  Currently, mike[32,33] are valid.  If
email to mikeN bounces, try mikeN+1.
--

Sun, 06 Apr 2003 03:00:00 GMT
Inversion

Quote:

> >> Anybody know how to invert a matrix ?
> >Get Sedgewick's book "Algorithms in C", or his earlier clearer
> >"Algorithms" (in Pascal).
> 1. Books.

> The _only_ good book I have ever seen on C code for numerical analysis
> is the book "Numerical Recipes in C".

Allow me to suggest the following book:

Matrix Computations (Johns Hopkins Series in the Mathematical Sciences)
by Gene H. Golub, Charles F. Van Loan
isbn 0801854148

Numerical Recipes is a real no-no compared to Holub and Van Loan when
we're

kind regards,

--

Mon, 07 Apr 2003 03:00:00 GMT
Inversion

Quote:

>> The _only_ good book I have ever seen on C code for numerical analysis
>> is the book "Numerical Recipes in C".

>Allow me to suggest the following book:

>    Matrix Computations (Johns Hopkins Series in the Mathematical Sciences)
>    by Gene H. Golub, Charles F. Van Loan
>    isbn 0801854148

>Numerical Recipes is a real no-no compared to Holub and Van Loan when

Let's put the matter to rest.  Golub and Van Loan is an excellent book,
but it contains no code, C or otherwise.  I would, however, _never_
recommend it to somebody who claimed not to be really clear on what a
matrix is, as the original poster claimed to be.  That is a book for the
numerical experts.

The "Numerical Recipes in C" book contains C code of a reasonable
quality, and the numerical analysis is quite good for starters.  Anybody
who knows C can probably use that book to get a linear equation solver
working.  If the programmer is not knowlegable about numerical linear
algebra, then of course his program will have limitations, however, I
suspect that the original poster will be more than satisfied with it.

When I said that I didn't like other books, I meant that I did not like
other books that claim to show how to implement numerical algorithms in
C.  Most of these books display a lack of understanging for numerical
analysis, and frequently also of programming.  The Numerical Recipes
books contain program source code, and are written by some of the worlds
leading numerical analysts, but are directed towards those who are not
experts, but wish to get a numerical algorithm running quickly.  Perhaps
the C code that they produce has something of a FORTRAN flavour; that's
because the book originally coded the algorithms in FORTRAN.  I don't
see this as being a problem.

Cheers,
Mike

--

address.  It is a mail alias.  Once spammed, the alias is deleted, and
the integer 'N' incremented.  Currently, mike[32,33] are valid.  If
email to mikeN bounces, try mikeN+1.
--

Mon, 07 Apr 2003 03:00:00 GMT
Inversion

Quote:
>When I said that I didn't like other books, I meant that I did not like
>other books that claim to show how to implement numerical algorithms in
>C.  Most of these books display a lack of understanging for numerical
>analysis, and frequently also of programming.  The Numerical Recipes
>books contain program source code, and are written by some of the worlds
>leading numerical analysts, but are directed towards those who are not
>experts, but wish to get a numerical algorithm running quickly.  Perhaps
>the C code that they produce has something of a FORTRAN flavour; that's
>because the book originally coded the algorithms in FORTRAN.  I don't
>see this as being a problem.

But the code style is horrible and the copyright limitations are pretty
draconian.

Francis Glassborow      Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
--

Wed, 09 Apr 2003 12:56:42 GMT
Inversion
: Anybody know how to invert a matrix ?
: I have no idea how to write an algorihm like that [snip]

Hello;

This is an opportunity to practice your C data structures.  Rather
than using just a 2-dimensional array to represent a matrix, consider
forming a simple data structure that contains an array of numbers, as
well as the number of rows and collumns.

Once you have the data structure written down, write a function to
dynamically allocate a matrix and return a pointer to that matrix, as well
as a function to free-up the matrix when you are done with it.

Write a few routines you will need, one to assign values to a matrix,
another to display the contents of a matrix.  With these in place, write
the matrix inversion function.

There are many many matrix inversion routines out there, some are for
special cases, some are fairly general purpose.  I'd recommend that you
look over a few and understand why the code works, then pick an example
and code it using your own data structures.

Jonathan Hill

--

Wed, 09 Apr 2003 13:01:51 GMT
Inversion

Quote:

..
> >The Numerical Recipes
> >books contain program source code, and are written by some of the worlds
> >leading numerical analysts, but are directed towards those who are not
> >experts, but wish to get a numerical algorithm running quickly.
...

> But the code style is horrible and the copyright limitations are pretty
> draconian.

Is there a good alternative compendium of no-nonsense C
implementations of numerical algorithms that you would recommend?

--
--Ed Cashin                     PGP public key:

Note: If you want me to send you email, don't munge your address.
--

Thu, 10 Apr 2003 13:00:29 GMT
Inversion

Quote:

> The "Numerical Recipes in C" book contains C code of a reasonable
> quality, ...

Certainly not in the first edition (I haven't seen any later editions).

Quote:
> the C code that they produce has something of a FORTRAN flavour;
> that's because the book originally coded the algorithms in FORTRAN.
> I don't see this as being a problem.

It's a problem because they decided that arrays had to be indexed
starting with 1 (as in Fortran) and invented a method of pretending
that they do that is not strictly conforming and can malfunction
horribly on some C implementations.
--

Thu, 10 Apr 2003 13:00:43 GMT
Inversion

Quote:

>: Anybody know how to invert a matrix ?
>: I have no idea how to write an algorihm like that [snip]

>Hello;

>     This is an opportunity to practice your C data structures.  Rather
>than using just a 2-dimensional array to represent a matrix, consider
>forming a simple data structure that contains an array of numbers, as
>well as the number of rows and collumns.

>     Once you have the data structure written down, write a function to
>dynamically allocate a matrix and return a pointer to that matrix, as well
>as a function to free-up the matrix when you are done with it.

I've seen a number of books that do this sort of thing.  The trouble is
that it is very slow.  Every access to entries of the matrix involve
calling functions.  Given that most numerical problems are compute
bound, and also that most of them also involve solving liner systems of
equations during each iteration, the efficiency of your solver is
(usually) the overriding consideration.

Cheers,
Mike

--

address.  It is a mail alias.  Once spammed, the alias is deleted, and
the integer 'N' incremented.  Currently, mike[33,34] are valid.  If
email to mikeN bounces, try mikeN+1.
--

Mon, 14 Apr 2003 13:31:13 GMT
Inversion

Quote:
>> But the code style is horrible and the copyright limitations are pretty
>> draconian.

>Is there a good alternative compendium of no-nonsense C
>implementations of numerical algorithms that you would recommend?

I wish there were, but note that most of the code was originally
generated by a FORTRAN to C converter

Francis Glassborow      Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
--

Mon, 14 Apr 2003 13:31:19 GMT
Inversion

Quote:

> Anybody know how to invert a matrix ?
> I have no idea how to write an algorihm like that since I barely even know
> matrix, so any help, if possible the whole program, would be appreciated.

Don't re-invent the wheel.  Any good book on Numerical Analysis should
discuss this.  You may find "Numerical Recipies in C" by Press,
Flannery, Teulosky and Vettering helpful.  One health warning --
although the book is good, some of the algorithms are less stable or
robust than "best practice" in numerical analysis.  Go to one of the
online archives such as Netlib which has C implementations of all
kinds of functions, including matrix inversion.

Keith Refson
--
Dr Keith Refson,        "Paradigm is a word too often used by those who would
Dept of Earth Sciences      like to have a new idea but cannot think of one."
Parks Road,                  -- Mervyn King, Deputy Governor, Bank of England
Oxford OX1 3PR, UK

earth.ox.ac.uk         Fax: 01865 272072
--

Tue, 15 Apr 2003 13:19:53 GMT

 Page 1 of 2 [ 18 post ] Go to page: [1] [2]

Relevant Pages