General eigenvalue problem proposal

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

General eigenvalue problem proposal

Rafael Gonzalez
I saw the project ideas list for octave for GSoC 2013 and I'm interested in the implementation of the eig function. I'm guessing that the goal is to achieve the different forms for calling the "eig" function in Matlab in order to ensure full portability. I've made a comparation and I'm listing the differences I found here:

Matlab:

d = eig(A)          Ax=λx
d = eig(A,B)       Ax=λBx
[V,D] = eig(A)
[V,D] = eig(A,'nobalance')*
[V,D] = eig(A,B)
[V,D] = eig(A,B,flag)*

Octave:

 -- Loadable Function: LAMBDA = eig (A)
 -- Loadable Function: LAMBDA = eig (A, B)
 -- Loadable Function: [V, LAMBDA] = eig (A)
 -- Loadable Function: [V, LAMBDA] = eig (A, B)

I was told that the generalized eigenvalue problem is not implemented yet, but isn't it the "eig(A, B)" call form? Anyways, Other difference I found was the possiblity to avoid the balance process for the eigenvalue problem and choosing wheter to use the cholesky factorization or the QZ method when B is singular, and maybe that's what is not implemented yet. Am I correct with the current overview on this?
Reply | Threaded
Open this post in threaded view
|

Re: General eigenvalue problem proposal

eem2314



On Wed, Apr 17, 2013 at 1:35 PM, Rafael Gonzalez <[hidden email]> wrote:
I saw the project ideas list for octave for GSoC 2013 and I'm interested in the implementation of the eig function. I'm guessing that the goal is to achieve the different forms for calling the "eig" function in Matlab in order to ensure full portability. I've made a comparation and I'm listing the differences I found here:

Matlab:

d = eig(A)          Ax=λx
d = eig(A,B)       Ax=λBx
[V,D] = eig(A)
[V,D] = eig(A,'nobalance')*
[V,D] = eig(A,B)
[V,D] = eig(A,B,flag)*

Octave:

 -- Loadable Function: LAMBDA = eig (A)
 -- Loadable Function: LAMBDA = eig (A, B)
 -- Loadable Function: [V, LAMBDA] = eig (A)
 -- Loadable Function: [V, LAMBDA] = eig (A, B)

I was told that the generalized eigenvalue problem is not implemented yet, but isn't it the "eig(A, B)" call form? Anyways, Other difference I found was the possiblity to avoid the balance process for the eigenvalue problem and choosing wheter to use the cholesky factorization or the QZ method when B is singular, and maybe that's what is not implemented yet. Am I correct with the current overview on this?
 
The generalized eigenvalue problem is treated in octave, though not quite the
same as in matlab.
It looks to me like balancing is not done at all in eig, unlike in ML where it is the
default for the standard eigenvalue problem (no indication in the ML doc if balancing
is done in the generalized case). In octave the user must use the "balance" command prior to eig(). What is not clear to me is how the correct eigenvectors are
recovered if the user does this. It would be easy to change the behaviour to
match ML by changing calls to *geev to *geevx. The balance/permute option
in *geevx allows for more options than ML allows so we could add more options
than just the 'nobalance' option. The same applies to *ggevx for the generalized case.
I've always felt that a refinement procedure after an eigensolution is better than
bothering the user with a decision whether or not to balance.

--
Ed Meyer
Reply | Threaded
Open this post in threaded view
|

Re: General eigenvalue problem proposal

Rafael Gonzalez
>>It looks to me like balancing is not done at all in eig, unlike in ML where it is the
>>default for the standard eigenvalue problem (no indication in the ML doc if balancing
>>is done in the generalized case).

Out of pure guess I'm thinking that Octave handles the generalized eigenvalue problem by solving a normal one with inv(B)*Ax=λx and I think that Matlab also does that as default, with the option of overriding it with the 'qz' flag and perform another method. So you're saying that the problem could be solved just by changing the calling form of the LAPACK routines?

2013/4/17 Ed Meyer <[hidden email]>



On Wed, Apr 17, 2013 at 1:35 PM, Rafael Gonzalez <[hidden email]> wrote:
I saw the project ideas list for octave for GSoC 2013 and I'm interested in the implementation of the eig function. I'm guessing that the goal is to achieve the different forms for calling the "eig" function in Matlab in order to ensure full portability. I've made a comparation and I'm listing the differences I found here:

Matlab:

d = eig(A)          Ax=λx
d = eig(A,B)       Ax=λBx
[V,D] = eig(A)
[V,D] = eig(A,'nobalance')*
[V,D] = eig(A,B)
[V,D] = eig(A,B,flag)*

Octave:

 -- Loadable Function: LAMBDA = eig (A)
 -- Loadable Function: LAMBDA = eig (A, B)
 -- Loadable Function: [V, LAMBDA] = eig (A)
 -- Loadable Function: [V, LAMBDA] = eig (A, B)

I was told that the generalized eigenvalue problem is not implemented yet, but isn't it the "eig(A, B)" call form? Anyways, Other difference I found was the possiblity to avoid the balance process for the eigenvalue problem and choosing wheter to use the cholesky factorization or the QZ method when B is singular, and maybe that's what is not implemented yet. Am I correct with the current overview on this?
 
The generalized eigenvalue problem is treated in octave, though not quite the
same as in matlab.
It looks to me like balancing is not done at all in eig, unlike in ML where it is the
default for the standard eigenvalue problem (no indication in the ML doc if balancing
is done in the generalized case). In octave the user must use the "balance" command prior to eig(). What is not clear to me is how the correct eigenvectors are
recovered if the user does this. It would be easy to change the behaviour to
match ML by changing calls to *geev to *geevx. The balance/permute option
in *geevx allows for more options than ML allows so we could add more options
than just the 'nobalance' option. The same applies to *ggevx for the generalized case.
I've always felt that a refinement procedure after an eigensolution is better than
bothering the user with a decision whether or not to balance.

--
Ed Meyer

Reply | Threaded
Open this post in threaded view
|

Re: General eigenvalue problem proposal

eem2314



On Thu, Apr 18, 2013 at 6:10 AM, Rafael Gonzalez <[hidden email]> wrote:
>>It looks to me like balancing is not done at all in eig, unlike in ML where it is the
>>default for the standard eigenvalue problem (no indication in the ML doc if balancing
>>is done in the generalized case).

Out of pure guess I'm thinking that Octave handles the generalized eigenvalue problem by solving a normal one with inv(B)*Ax=λx and I think that Matlab also does that as default, with the option of overriding it with the 'qz' flag and perform another method. So you're saying that the problem could be solved just by changing the calling form of the LAPACK routines?


In octave the generalized problem is solved using *sygv if the matrices are symmetric.
This does a cholesky factorization of B and uses the factors to transform the problem
to a standard symmetric problem - just doing inv(B)*A loses the symmetry.
If the matrices are nonsymmetric the QZ algorithm is used.
All the routines used for eigenvalues have extended versions with names ending
in 'x', e.g. dsygvx, which allow for more control over the solution process. For
nonsymmetric problems they allow for balancing by permuting and/or scaling the
matrices. The non-extended versions used in octave only permute the matrices.

The reason ML provides the option to turn off balancing is that scaling (but not
permuting) can cause numerical problems if the matrix has tiny elements. The
LAPACK manual does not discuss this drawback but the ML document does.
--
Ed Meyer