Symmetric matrices only!

Symmetric matrices only!

[amado.alves]

The eigenvector solvers in Ada.Numerics.Generic_Real_Arrays require
*symmetric* matrices! This is extremely silly. The world is full of
nonsymmetric matrices. I've got a bunch of them to solve. Some very
large, e.g. 1000x1000. Suggestions welcome. Thanks a lot.

Re: Symmetric matrices only!

[Adam Beneschan]

On Apr 17, 6:16 am, amado.al...@gmail.com wrote:
> The eigenvector solvers in Ada.Numerics.Generic_Real_Arrays require
> *symmetric* matrices! This is extremely silly. The world is full of
> nonsymmetric matrices. I've got a bunch of them to solve. Some very
> large, e.g. 1000x1000. Suggestions welcome. Thanks a lot.

We're in an area where I have no mathematical knowledge.  However, I
can quote something from AI95-296, which might explain why an
"extremely silly" decision was made:

'We considered providing subprograms for the determination of
eigenvalues and
eigenvectors of general real and complex matrices. Such matrices can
have
complex eigenvalues and therefore provision for these would have to be
in the
complex package. However, there are mathematical difficulties with
these general
cases which are in strong contrast to the real symmetric and Hermitian
matrices.
Thus, Numerical Recipes by Press, Flannery, Teukolsky and Vetterling
says
regarding the real case:

"The algorithms for symmetric matrices ... are highly satisfactory in
practice.
By contrast, it is impossible to design equally satisfactory
algorithms for the
nonsymmetric case. There are two reasons for this. First, the
eigenvalues of a
nonsymmetric matrix can be very sensitive to small changes in the
matrix
elements. Second, the matrix itself can be defective so that there is
no
complete set of eigenvectors. We emphasize that these difficulties are
intrinsic
properties of certain nonsymmetric matrices, and no numerical
procedure can cure
them."'

In the discussion section of the AI there's this, from John Barnes:

"Moreover, the eigenvalues and vectors of
nonsymmetric, non-Hermitian matrices have been removed because of
potential
computational difficulties."

I have no idea what all this means, but it doesn't sound silly to me.

                                     -- Adam

Re: Symmetric matrices only!

[Dmitry A. Kazakov]

On Thu, 17 Apr 2008 08:25:26 -0700 (PDT), Adam Beneschan wrote:

> On Apr 17, 6:16 am, amado.al...@gmail.com wrote:

>> The eigenvector solvers in Ada.Numerics.Generic_Real_Arrays require
>> *symmetric* matrices! This is extremely silly. The world is full of
>> nonsymmetric matrices. I've got a bunch of them to solve. Some very
>> large, e.g. 1000x1000. Suggestions welcome. Thanks a lot.

In my times it was "huge". (:-)) I"m afraid you should turn to special
literature and implement a suitable method by yourself.

> We're in an area where I have no mathematical knowledge.  However, I
> can quote something from AI95-296, which might explain why an
> "extremely silly" decision was made:

[...]

It is a long time since I dealt with numerical linear algebra, but I well
remember that eigenvalues and/or eigenvectors is a complex numerical
problem, which does not have just one, best solution method. There are many
special case matrices, sparse matrices etc.

It is strange that the package does not mandate neither the method, nor the
accuracy. I would expect a design with several child packages implementing
different methods for special matrix cases, as well as means for
checkpointing when dealing with large matrices.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Symmetric matrices only!

[smsomething]

On Apr 18, 1:16 am, amado.al...@gmail.com wrote:
> The eigenvector solvers in Ada.Numerics.Generic_Real_Arrays require
> *symmetric* matrices! This is extremely silly. The world is full of
> nonsymmetric matrices. I've got a bunch of them to solve. Some very
> large, e.g. 1000x1000. Suggestions welcome. Thanks a lot.

Providing support for solving eigenvectors for general matrices
without restrictions would be a very complicated task, and I can
understand why the language designers provided the limited support
they have. Ada provides a rather basic set of solvers, useable in
straight-forward problems. This is not particularly silly at all -
it's a pragmatic approach to what is a very difficult general problem.
Having said that, I do use the Ada built-in solvers, and they're very
useful where I can't be bothered getting access to specialised
routines, or where there is no necessity to do so. When I need
something better, I use a routine that has been proven to work in the
specialised situation I am dealing with.

If you (potentially) need to find the eigenvalues of non-symmetric
matrices of 1000x1000, then your need is highly specialised, and you
need to seek out the highly-specialised solutions that have been
developed, and that are widely available. Some will be in C/C++, but
more likely they are in FORTRAN, but the interfacing issues with Ada
are (usually) not complicated.

You could start with GSL (www.gnu.org/software/gsl), which has a
variety of eigensystem solvers, including a set for real asymmetric
matrices. Also look at NETLIB (www.netlib.org). Once you've been
through these, you'll have a better idea what kind of problem you are
up against, and whether you need to seek straight-forward or
specialised routines.

Unfortunately, you havn't specified whether your asymmetric matrices
are real or complex, or whether the matrix itself has any other
construction properties, or whether it is sparse. Answers to these
questions could drastically alter the advice you would be given.

Overall, the answer to your problem for calculating (or, better,
"estimating") eigenvalues is out there somewhere, and the various
solutions can (in general) be accessed from Ada.

Good luck
SM

Re: Symmetric matrices only!

[Gautier]

amado.alves@gmail.com:

> The eigenvector solvers in Ada.Numerics.Generic_Real_Arrays require
> *symmetric* matrices! This is extremely silly. The world is full of
> nonsymmetric matrices. I've got a bunch of them to solve. Some very
> large, e.g. 1000x1000. Suggestions welcome. Thanks a lot.

As other people answered, solving a symmetric matrix is another science than a 
asymmetric one. But also when the matrices get big, other storages (than array 
(Integer range <>, Integer range <>) of...) can be a better solution, like band 
or sparse matrices. In some areas a 10_000 x 10_000 matrix is a toy one, for 
testing small examples (e.g. solving a physics equation on a 100x100 grid)...
______________________________________________________________
Gautier         -- http://www.mysunrise.ch/users/gdm/index.htm
Ada programming -- http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!

Re: Symmetric matrices only!

[Ken Thomas]

On Apr 18, 5:30 am, Gautier <gaut...@fakeaddress.nil> wrote:
> amado.al...@gmail.com:
>
> > The eigenvector solvers in Ada.Numerics.Generic_Real_Arrays require
> > *symmetric* matrices! This is extremely silly. The world is full of
> > nonsymmetric matrices. I've got a bunch of them to solve. Some very
> > large, e.g. 1000x1000. Suggestions welcome. Thanks a lot.
>
> As other people answered, solving a symmetric matrix is another science than a
> asymmetric one. But also when the matrices get big, other storages (than array
> (Integer range <>, Integer range <>) of...) can be a better solution, like band
> or sparse matrices. In some areas a 10_000 x 10_000 matrix is a toy one, for
> testing small examples (e.g. solving a physics equation on a 100x100 grid)...
> ______________________________________________________________
> Gautier         --http://www.mysunrise.ch/users/gdm/index.htm
> Ada programming --http://www.mysunrise.ch/users/gdm/gsoft.htm
>
> NB: For a direct answer, e-mail address on the Web site!

What you can do is write an interface to the LAPACK routine _GEEV (or
similar); it means needing an installation of LAPACK and BLAS. But if
you are using Generic_Real_Arrays you will need to link up with these
libraries anyway.

Duncan Sands produced bindings to BLAS and I extended some to cover
the LAPACK material I needed. They are not complete  just created on
demand. I could send these if they would help.

Ada is very good in the way it can define interfaces to numerical
software.

Re: Symmetric matrices only!

[amado.alves]

Thanks all for the excellent replies.

Incidentally, I found out that I do *not* have Generic_Real_Arrays on
my GNAT GPL 2006 on Mac OS X 10.4 anyway, so now I have the added
problem of installing GPL 2007 in the hopes... (I have other problems
that I can solve with the Solve function, and eventually I may
reformat the eigenproblem likewise, or work with two symmetric
matrices in lieu of one nonsymmetric).

Or else I shall try the BLAS or another tool suggested here.

For the record, the matrices are of real numbers, they represent
hypertexts, and normally the large matrices are sparse.

Thanks a lot.

Re: Symmetric matrices only!

[amado.alves]

> "Moreover, the eigenvalues and vectors of
> nonsymmetric, non-Hermitian matrices have been removed because of
> potential
> computational difficulties." (Barnes)
>
> I have no idea what all this means, but it doesn't sound silly to me. (Adam)

Continues to sound silly to me (ok maybe not extremely;-) Yes for
certain matrices the eigenproblem is hard, but there are methods to
solve it satisfactorily for other certain matrices including large
ones e.g. the "power method."

And computing the determinant can also be very hard but the function
is there! To use with caution!--which approach should extend to eigen.

Hey, this reminds me, I think there is a way to solve eigen using
determinants, so problem solved... if I had the library in the first
place (GPL 2007 does not seem to have it)... arg!"#$%&/()=

Re: Symmetric matrices only!

[amado.alves]

> Duncan Sands produced bindings to BLAS and I extended some to cover
> the LAPACK material I needed. They are not complete  just created on
> demand. I could send these if they would help.

You're my saviour! No need to send material, but I'd really appreciate
pointers to the required material and how to edit it and link in on
Mac Os X. I've got a file here named "libLAPACK.dylib" shouldn't that
be it? How do I link? I tried

gnatmake example1 -l/Developer/SDKs/MacOSX10.4u.sdk/System/Library/
Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/
Versions/A/libLAPACK.dylib

But still got:

Undefined symbols:
_isamax_
_sasum_
_saxpy_
...

Thanks.

Re: Symmetric matrices only!

[Jerry]

On Apr 18, 8:19 am, amado.al...@gmail.com wrote:
> Thanks all for the excellent replies.
>
> Incidentally, I found out that I do *not* have Generic_Real_Arrays on
> my GNAT GPL 2006 on Mac OS X 10.4 anyway, so now I have the added
> problem of installing GPL 2007 in the hopes... (I have other problems
> that I can solve with the Solve function, and eventually I may
> reformat the eigenproblem likewise, or work with two symmetric
> matrices in lieu of one nonsymmetric).
>
> Or else I shall try the BLAS or another tool suggested here.
>
> For the record, the matrices are of real numbers, they represent
> hypertexts, and normally the large matrices are sparse.
>
> Thanks a lot.

By the way, you may encounter problems getting the Vector-Matrix
(Annex G.3) stuff to working on OS X. The problem has been worked out
but is not yet part of the installer. I recommend that you check out
macada.org; join the list or just check the archives for April 15,
2008, where this was most recently discussed.

Jerry

Re: Symmetric matrices only!

[Jerry]

On Apr 18, 9:27 am, amado.al...@gmail.com wrote:
> > Duncan Sands produced bindings to BLAS and I extended some to cover
> > the LAPACK material I needed. They are not complete  just created on
> > demand. I could send these if they would help.
>
> You're my saviour! No need to send material, but I'd really appreciate
> pointers to the required material and how to edit it and link in on
> Mac Os X. I've got a file here named "libLAPACK.dylib" shouldn't that
> be it? How do I link? I tried
>
> gnatmake example1 -l/Developer/SDKs/MacOSX10.4u.sdk/System/Library/
> Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/
> Versions/A/libLAPACK.dylib
>
> But still got:
>
> Undefined symbols:
> _isamax_
> _sasum_
> _saxpy_
> ...
>
> Thanks.

See my response to your earlier post above about getting your
installing going.
Jerry

Re: Symmetric matrices only!

[Jerry]

On Apr 18, 9:27 am, amado.al...@gmail.com wrote:
> > Duncan Sands produced bindings to BLAS and I extended some to cover
> > the LAPACK material I needed. They are not complete  just created on
> > demand. I could send these if they would help.
>
> You're my saviour! No need to send material, but I'd really appreciate
> pointers to the required material and how to edit it and link in on
> Mac Os X. I've got a file here named "libLAPACK.dylib" shouldn't that
> be it? How do I link? I tried
>
> gnatmake example1 -l/Developer/SDKs/MacOSX10.4u.sdk/System/Library/
> Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/
> Versions/A/libLAPACK.dylib
>
> But still got:
>
> Undefined symbols:
> _isamax_
> _sasum_
> _saxpy_
> ...
>
> Thanks.

See my response to your earlier post above about getting your
installing going.
Jerry

Re: Symmetric matrices only!

[amado.alves]

> > Incidentally, I found out that I do *not* have Generic_Real_Arrays on
> > my GNAT GPL 2006 on Mac OS X 10.4 anyway... (Marius)

> By the way, you may encounter problems getting the Vector-Matrix
> (Annex G.3) stuff to working on OS X. The problem has been worked out
> but is not yet part of the installer. I recommend that you check out
> macada.org; join the list or just check the archives for April 15,
> 2008, where this was most recently discussed.
>
> Jerry

Sweet! Jerry's notes on the MacAda list solve this problem. Highly
recommended :-)