/* eigen/hermv.c
*
* Copyright (C) 2001, 2007 Brian Gough
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or (at
* your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#include <config.h>
#include <stdlib.h>
#include <gsl/gsl_math.h>
#include <gsl/gsl_vector.h>
#include <gsl/gsl_matrix.h>
#include <gsl/gsl_complex_math.h>
#include <gsl/gsl_linalg.h>
#include <gsl/gsl_eigen.h>
/* Compute eigenvalues/eigenvectors of complex hermitian matrix using
reduction to real symmetric tridiagonal form, followed by QR
iteration with implicit shifts.
See Golub & Van Loan, "Matrix Computations" (3rd ed), Section 8.3 */
#include "qrstep.c"
gsl_eigen_hermv_workspace *
gsl_eigen_hermv_alloc (const size_t n)
{
gsl_eigen_hermv_workspace * w ;
if (n == 0)
{
GSL_ERROR_NULL ("matrix dimension must be positive integer", GSL_EINVAL);
}
w = (gsl_eigen_hermv_workspace *) malloc (sizeof(gsl_eigen_hermv_workspace));
if (w == 0)
{
GSL_ERROR_NULL ("failed to allocate space for workspace", GSL_ENOMEM);
}
w->d = (double *) malloc (n * sizeof (double));
if (w->d == 0)
{
free (w);
GSL_ERROR_NULL ("failed to allocate space for diagonal", GSL_ENOMEM);
}
w->sd = (double *) malloc (n * sizeof (double));
if (w->sd == 0)
{
free (w->d);
free (w);
GSL_ERROR_NULL ("failed to allocate space for subdiagonal", GSL_ENOMEM);
}
w->tau = (double *) malloc (2 * n * sizeof (double));
if (w->tau == 0)
{
free (w->sd);
free (w->d);
free (w);
GSL_ERROR_NULL ("failed to allocate space for tau", GSL_ENOMEM);
}
w->gc = (double *) malloc (n * sizeof (double));
if (w->gc == 0)
{
free (w->tau);
free (w->sd);
free (w->d);
free (w);
GSL_ERROR_NULL ("failed to allocate space for cosines", GSL_ENOMEM);
}
w->gs = (double *) malloc (n * sizeof (double));
if (w->gs == 0)
{
free (w->gc);
free (w->tau);
free (w->sd);
free (w->d);
free (w);
GSL_ERROR_NULL ("failed to allocate space for sines", GSL_ENOMEM);
}
w->size = n;
return w;
}
void
gsl_eigen_hermv_free (gsl_eigen_hermv_workspace * w)
{
RETURN_IF_NULL (w);
free (w->gs);
free (w->gc);
free (w->tau);
free (w->sd);
free (w->d);
free (w);
}
int
gsl_eigen_hermv (gsl_matrix_complex * A, gsl_vector * eval,
gsl_matrix_complex * evec,
gsl_eigen_hermv_workspace * w)
{
if (A->size1 != A->size2)
{
GSL_ERROR ("matrix must be square to compute eigenvalues", GSL_ENOTSQR);
}
else if (eval->size != A->size1)
{
GSL_ERROR ("eigenvalue vector must match matrix size", GSL_EBADLEN);
}
else if (evec->size1 != A->size1 || evec->size2 != A->size1)
{
GSL_ERROR ("eigenvector matrix must match matrix size", GSL_EBADLEN);
}
else
{
const size_t N = A->size1;
double *const d = w->d;
double *const sd = w->sd;
size_t a, b;
/* handle special case */
if (N == 1)
{
gsl_complex A00 = gsl_matrix_complex_get (A, 0, 0);
gsl_vector_set (eval, 0, GSL_REAL(A00));
gsl_matrix_complex_set (evec, 0, 0, GSL_COMPLEX_ONE);
return GSL_SUCCESS;
}
/* Transform the matrix into a symmetric tridiagonal form */
{
gsl_vector_view d_vec = gsl_vector_view_array (d, N);
gsl_vector_view sd_vec = gsl_vector_view_array (sd, N - 1);
gsl_vector_complex_view tau_vec = gsl_vector_complex_view_array (w->tau, N-1);
gsl_linalg_hermtd_decomp (A, &tau_vec.vector);
gsl_linalg_hermtd_unpack (A, &tau_vec.vector, evec, &d_vec.vector, &sd_vec.vector);
}
/* Make an initial pass through the tridiagonal decomposition
to remove off-diagonal elements which are effectively zero */
chop_small_elements (N, d, sd);
/* Progressively reduce the matrix until it is diagonal */
b = N - 1;
while (b > 0)
{
if (sd[b - 1] == 0.0 || isnan(sd[b - 1]))
{
b--;
continue;
}
/* Find the largest unreduced block (a,b) starting from b
and working backwards */
a = b - 1;
while (a > 0)
{
if (sd[a - 1] == 0.0)
{
break;
}
a--;
}
{
size_t i;
const size_t n_block = b - a + 1;
double *d_block = d + a;
double *sd_block = sd + a;
double * const gc = w->gc;
double * const gs = w->gs;
/* apply QR reduction with implicit deflation to the
unreduced block */
qrstep (n_block, d_block, sd_block, gc, gs);
/* Apply Givens rotation Gij(c,s) to matrix Q, Q <- Q G */
for (i = 0; i < n_block - 1; i++)
{
const double c = gc[i], s = gs[i];
size_t k;
for (k = 0; k < N; k++)
{
gsl_complex qki = gsl_matrix_complex_get (evec, k, a + i);
gsl_complex qkj = gsl_matrix_complex_get (evec, k, a + i + 1);
/* qki <= qki * c - qkj * s */
/* qkj <= qki * s + qkj * c */
gsl_complex x1 = gsl_complex_mul_real(qki, c);
gsl_complex y1 = gsl_complex_mul_real(qkj, -s);
gsl_complex x2 = gsl_complex_mul_real(qki, s);
gsl_complex y2 = gsl_complex_mul_real(qkj, c);
gsl_complex qqki = gsl_complex_add(x1, y1);
gsl_complex qqkj = gsl_complex_add(x2, y2);
gsl_matrix_complex_set (evec, k, a + i, qqki);
gsl_matrix_complex_set (evec, k, a + i + 1, qqkj);
}
}
/* remove any small off-diagonal elements */
chop_small_elements (n_block, d_block, sd_block);
}
}
{
gsl_vector_view d_vec = gsl_vector_view_array (d, N);
gsl_vector_memcpy (eval, &d_vec.vector);
}
return GSL_SUCCESS;
}
}