/*************************************************************************

Copyright (c) 1992-2007 The University of Tennessee.  All rights reserved.



Contributors:

    * Sergey Bochkanov (ALGLIB project). Translation from FORTRAN to

      pseudocode.



See subroutines comments for additional copyrights.



Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are

met:



- Redistributions of source code must retain the above copyright

  notice, this list of conditions and the following disclaimer.



- Redistributions in binary form must reproduce the above copyright

  notice, this list of conditions and the following disclaimer listed

  in this license in the documentation and/or other materials

  provided with the distribution.



- Neither the name of the copyright holders nor the names of its

  contributors may be used to endorse or promote products derived from

  this software without specific prior written permission.



THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*************************************************************************/



#ifndef _nsevd_h

#define _nsevd_h



#include "capd/alglib/ap.h"


#include "capd/alglib/blas.h"
#include "capd/alglib/reflections.h"
#include "capd/alglib/rotations.h"
#include "capd/alglib/hsschur.h"
#include "capd/alglib/hessenberg.h"




/*************************************************************************

Finding eigenvalues and eigenvectors of a general matrix



The algorithm finds eigenvalues and eigenvectors of a general matrix by

using the QR algorithm with multiple shifts. The algorithm can find

eigenvalues and both left and right eigenvectors.



The right eigenvector is a vector x such that A*x = w*x, and the left

eigenvector is a vector y such that y'*A = w*y' (here y' implies a complex

conjugate transposition of vector y).



Input parameters:

    A       -   matrix. Array whose indexes range within [0..N-1, 0..N-1].

    N       -   size of matrix A.

    VNeeded -   flag controlling whether eigenvectors are needed or not.

                If VNeeded is equal to:

                 * 0, eigenvectors are not returned;

                 * 1, right eigenvectors are returned;

                 * 2, left eigenvectors are returned;

                 * 3, both left and right eigenvectors are returned.



Output parameters:

    WR      -   real parts of eigenvalues.

                Array whose index ranges within [0..N-1].

    WR      -   imaginary parts of eigenvalues.

                Array whose index ranges within [0..N-1].

    VL, VR  -   arrays of left and right eigenvectors (if they are needed).

                If WI[i]=0, the respective eigenvalue is a real number,

                and it corresponds to the column number I of matrices VL/VR.

                If WI[i]>0, we have a pair of complex conjugate numbers with

                positive and negative imaginary parts:

                    the first eigenvalue WR[i] + sqrt(-1)*WI[i];

                    the second eigenvalue WR[i+1] + sqrt(-1)*WI[i+1];

                    WI[i]>0

                    WI[i+1] = -WI[i] < 0

                In that case, the eigenvector  corresponding to the first

                eigenvalue is located in i and i+1 columns of matrices

                VL/VR (the column number i contains the real part, and the

                column number i+1 contains the imaginary part), and the vector

                corresponding to the second eigenvalue is a complex conjugate to

                the first vector.

                Arrays whose indexes range within [0..N-1, 0..N-1].



Result:

    True, if the algorithm has converged.

    False, if the algorithm has not converged.



Note 1:

    Some users may ask the following question: what if WI[N-1]>0?

    WI[N] must contain an eigenvalue which is complex conjugate to the

    N-th eigenvalue, but the array has only size N?

    The answer is as follows: such a situation cannot occur because the

    algorithm finds a pairs of eigenvalues, therefore, if WI[i]>0, I is

    strictly less than N-1.



Note 2:

    The algorithm performance depends on the value of the internal parameter

    NS of the InternalSchurDecomposition subroutine which defines the number

    of shifts in the QR algorithm (similarly to the block width in block-matrix

    algorithms of linear algebra). If you require maximum performance

    on your machine, it is recommended to adjust this parameter manually.





See also the InternalTREVC subroutine.



The algorithm is based on the LAPACK 3.0 library.

*************************************************************************/

bool rmatrixevd(ap::real_2d_array a,

     int n,

     int vneeded,

     ap::real_1d_array& wr,

     ap::real_1d_array& wi,

     ap::real_2d_array& vl,

     ap::real_2d_array& vr);





/*************************************************************************

Obsolete 1-based subroutine

*************************************************************************/

bool nonsymmetricevd(ap::real_2d_array a,

     int n,

     int vneeded,

     ap::real_1d_array& wr,

     ap::real_1d_array& wi,

     ap::real_2d_array& vl,

     ap::real_2d_array& vr);





#endif

