|
Packit |
67cb25 |
/* eigen/symm.c
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* Copyright (C) 2001, 2007 Brian Gough
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* This program is free software; you can redistribute it and/or modify
|
|
Packit |
67cb25 |
* it under the terms of the GNU General Public License as published by
|
|
Packit |
67cb25 |
* the Free Software Foundation; either version 3 of the License, or (at
|
|
Packit |
67cb25 |
* your option) any later version.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* This program is distributed in the hope that it will be useful, but
|
|
Packit |
67cb25 |
* WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
67cb25 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit |
67cb25 |
* General Public License for more details.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* You should have received a copy of the GNU General Public License
|
|
Packit |
67cb25 |
* along with this program; if not, write to the Free Software
|
|
Packit |
67cb25 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
#include <config.h>
|
|
Packit |
67cb25 |
#include <stdlib.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_math.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_vector.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_matrix.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_linalg.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_eigen.h>
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Compute eigenvalues/eigenvectors of real symmetric matrix using
|
|
Packit |
67cb25 |
reduction to tridiagonal form, followed by QR iteration with
|
|
Packit |
67cb25 |
implicit shifts.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
See Golub & Van Loan, "Matrix Computations" (3rd ed), Section 8.3
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
#include "qrstep.c"
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_eigen_symm_workspace *
|
|
Packit |
67cb25 |
gsl_eigen_symm_alloc (const size_t n)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
gsl_eigen_symm_workspace *w;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (n == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR_NULL ("matrix dimension must be positive integer",
|
|
Packit |
67cb25 |
GSL_EINVAL);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
w = ((gsl_eigen_symm_workspace *)
|
|
Packit |
67cb25 |
malloc (sizeof (gsl_eigen_symm_workspace)));
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (w == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR_NULL ("failed to allocate space for workspace", GSL_ENOMEM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
w->d = (double *) malloc (n * sizeof (double));
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (w->d == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR_NULL ("failed to allocate space for diagonal", GSL_ENOMEM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
w->sd = (double *) malloc (n * sizeof (double));
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (w->sd == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR_NULL ("failed to allocate space for subdiagonal", GSL_ENOMEM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
w->size = n;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return w;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
void
|
|
Packit |
67cb25 |
gsl_eigen_symm_free (gsl_eigen_symm_workspace * w)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
RETURN_IF_NULL (w);
|
|
Packit |
67cb25 |
free (w->sd);
|
|
Packit |
67cb25 |
free (w->d);
|
|
Packit |
67cb25 |
free (w);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_eigen_symm (gsl_matrix * A, gsl_vector * eval,
|
|
Packit |
67cb25 |
gsl_eigen_symm_workspace * w)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (A->size1 != A->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix must be square to compute eigenvalues", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (eval->size != A->size1)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("eigenvalue vector must match matrix size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (A->size1 != w->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix does not match workspace", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
const size_t N = A->size1;
|
|
Packit |
67cb25 |
double *const d = w->d;
|
|
Packit |
67cb25 |
double *const sd = w->sd;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
size_t a, b;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* handle special case */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (N == 1)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
double A00 = gsl_matrix_get (A, 0, 0);
|
|
Packit |
67cb25 |
gsl_vector_set (eval, 0, A00);
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* use sd as the temporary workspace for the decomposition,
|
|
Packit |
67cb25 |
since we can discard the tau result immediately if we are not
|
|
Packit |
67cb25 |
computing eigenvectors */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
gsl_vector_view d_vec = gsl_vector_view_array (d, N);
|
|
Packit |
67cb25 |
gsl_vector_view sd_vec = gsl_vector_view_array (sd, N - 1);
|
|
Packit |
67cb25 |
gsl_vector_view tau = gsl_vector_view_array (sd, N - 1);
|
|
Packit |
67cb25 |
gsl_linalg_symmtd_decomp (A, &tau.vector);
|
|
Packit |
67cb25 |
gsl_linalg_symmtd_unpack_T (A, &d_vec.vector, &sd_vec.vector);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Make an initial pass through the tridiagonal decomposition
|
|
Packit |
67cb25 |
to remove off-diagonal elements which are effectively zero */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
chop_small_elements (N, d, sd);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Progressively reduce the matrix until it is diagonal */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
b = N - 1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
while (b > 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (sd[b - 1] == 0.0 || isnan(sd[b - 1]))
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
b--;
|
|
Packit |
67cb25 |
continue;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Find the largest unreduced block (a,b) starting from b
|
|
Packit |
67cb25 |
and working backwards */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
a = b - 1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
while (a > 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (sd[a - 1] == 0.0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
break;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
a--;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
const size_t n_block = b - a + 1;
|
|
Packit |
67cb25 |
double *d_block = d + a;
|
|
Packit |
67cb25 |
double *sd_block = sd + a;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* apply QR reduction with implicit deflation to the
|
|
Packit |
67cb25 |
unreduced block */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
qrstep (n_block, d_block, sd_block, NULL, NULL);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* remove any small off-diagonal elements */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
chop_small_elements (n_block, d_block, sd_block);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
gsl_vector_view d_vec = gsl_vector_view_array (d, N);
|
|
Packit |
67cb25 |
gsl_vector_memcpy (eval, &d_vec.vector);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|