Prev: Memory leak in BLAS/LINPACK - GNAT on OS X
Next: Address attribute of an overloaded function
From: amado.alves on 17 Apr 2008 09:16
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.
From: Adam Beneschan on 17 Apr 2008 11:25
On Apr 17, 6:16 am, amado.al...(a)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
From: Dmitry A. Kazakov on 17 Apr 2008 12:55
On Thu, 17 Apr 2008 08:25:26 -0700 (PDT), Adam Beneschan wrote:

> On Apr 17, 6:16 am, amado.al...(a)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
From: smsomething on 17 Apr 2008 21:34
On Apr 18, 1:16 am, amado.al...(a)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
From: Gautier on 18 Apr 2008 00:30
amado.alves(a)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!
 |  Next  |  Last
Pages: 1 2 3
Prev: Memory leak in BLAS/LINPACK - GNAT on OS X
Next: Address attribute of an overloaded function