|
Packit |
67cb25 |
/* linalg/lu.c
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007, 2009 Gerard Jungman, 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 |
/* Author: G. Jungman */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
#include <config.h>
|
|
Packit |
67cb25 |
#include <stdlib.h>
|
|
Packit |
67cb25 |
#include <string.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_permute_vector.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_blas.h>
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
#include <gsl/gsl_linalg.h>
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
#define REAL double
|
|
Packit |
67cb25 |
static int singular (const gsl_matrix * LU);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Factorise a general N x N matrix A into,
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* P A = L U
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* where P is a permutation matrix, L is unit lower triangular and U
|
|
Packit |
67cb25 |
* is upper triangular.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* L is stored in the strict lower triangular part of the input
|
|
Packit |
67cb25 |
* matrix. The diagonal elements of L are unity and are not stored.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* U is stored in the diagonal and upper triangular part of the
|
|
Packit |
67cb25 |
* input matrix.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* P is stored in the permutation p. Column j of P is column k of the
|
|
Packit |
67cb25 |
* identity matrix, where k = permutation->data[j]
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* signum gives the sign of the permutation, (-1)^n, where n is the
|
|
Packit |
67cb25 |
* number of interchanges in the permutation.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* See Golub & Van Loan, Matrix Computations, Algorithm 3.4.1 (Gauss
|
|
Packit |
67cb25 |
* Elimination with Partial Pivoting).
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_linalg_LU_decomp (gsl_matrix * A, gsl_permutation * p, int *signum)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (A->size1 != A->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("LU decomposition requires square matrix", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (p->size != A->size1)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("permutation length must match matrix size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
const size_t N = A->size1;
|
|
Packit |
67cb25 |
size_t i, j, k;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
*signum = 1;
|
|
Packit |
67cb25 |
gsl_permutation_init (p);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (j = 0; j < N - 1; j++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
/* Find maximum in the j-th column */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
REAL ajj, max = fabs (gsl_matrix_get (A, j, j));
|
|
Packit |
67cb25 |
size_t i_pivot = j;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = j + 1; i < N; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
REAL aij = fabs (gsl_matrix_get (A, i, j));
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (aij > max)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
max = aij;
|
|
Packit |
67cb25 |
i_pivot = i;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (i_pivot != j)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
gsl_matrix_swap_rows (A, j, i_pivot);
|
|
Packit |
67cb25 |
gsl_permutation_swap (p, j, i_pivot);
|
|
Packit |
67cb25 |
*signum = -(*signum);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
ajj = gsl_matrix_get (A, j, j);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (ajj != 0.0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
for (i = j + 1; i < N; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
REAL aij = gsl_matrix_get (A, i, j) / ajj;
|
|
Packit |
67cb25 |
gsl_matrix_set (A, i, j, aij);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (k = j + 1; k < N; k++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
REAL aik = gsl_matrix_get (A, i, k);
|
|
Packit |
67cb25 |
REAL ajk = gsl_matrix_get (A, j, k);
|
|
Packit |
67cb25 |
gsl_matrix_set (A, i, k, aik - aij * ajk);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_linalg_LU_solve (const gsl_matrix * LU, const gsl_permutation * p, const gsl_vector * b, gsl_vector * x)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (LU->size1 != LU->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("LU matrix must be square", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != p->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("permutation length must match matrix size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != b->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix size must match b size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size2 != x->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix size must match solution size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (singular (LU))
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix is singular", GSL_EDOM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
int status;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Copy x <- b */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_vector_memcpy (x, b);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Solve for x */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
status = gsl_linalg_LU_svx (LU, p, x);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return status;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_linalg_LU_svx (const gsl_matrix * LU, const gsl_permutation * p, gsl_vector * x)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (LU->size1 != LU->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("LU matrix must be square", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != p->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("permutation length must match matrix size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != x->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix size must match solution/rhs size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (singular (LU))
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix is singular", GSL_EDOM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
/* Apply permutation to RHS */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_permute_vector (p, x);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Solve for c using forward-substitution, L c = P b */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_blas_dtrsv (CblasLower, CblasNoTrans, CblasUnit, LU, x);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Perform back-substitution, U x = c */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_blas_dtrsv (CblasUpper, CblasNoTrans, CblasNonUnit, LU, x);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_linalg_LU_refine (const gsl_matrix * A, const gsl_matrix * LU, const gsl_permutation * p, const gsl_vector * b, gsl_vector * x, gsl_vector * work)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (A->size1 != A->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix a must be square", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
if (LU->size1 != LU->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("LU matrix must be square", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (A->size1 != LU->size2)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("LU matrix must be decomposition of a", GSL_ENOTSQR);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != p->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("permutation length must match matrix size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != b->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix size must match b size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != x->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix size must match solution size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (LU->size1 != work->size)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix size must match workspace size", GSL_EBADLEN);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (singular (LU))
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix is singular", GSL_EDOM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
int status;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Compute residual = (A * x - b) */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_vector_memcpy (work, b);
|
|
Packit |
67cb25 |
gsl_blas_dgemv (CblasNoTrans, 1.0, A, x, -1.0, work);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Find correction, delta = - (A^-1) * residual, and apply it */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
status = gsl_linalg_LU_svx (LU, p, work);
|
|
Packit |
67cb25 |
gsl_blas_daxpy (-1.0, work, x);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return status;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_linalg_LU_invert (const gsl_matrix * LU, const gsl_permutation * p, gsl_matrix * inverse)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, n = LU->size1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int status = GSL_SUCCESS;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (singular (LU))
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("matrix is singular", GSL_EDOM);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
gsl_matrix_set_identity (inverse);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 0; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
gsl_vector_view c = gsl_matrix_column (inverse, i);
|
|
Packit |
67cb25 |
int status_i = gsl_linalg_LU_svx (LU, p, &(c.vector));
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (status_i)
|
|
Packit |
67cb25 |
status = status_i;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return status;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
double
|
|
Packit |
67cb25 |
gsl_linalg_LU_det (gsl_matrix * LU, int signum)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, n = LU->size1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
double det = (double) signum;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 0; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
det *= gsl_matrix_get (LU, i, i);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return det;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
double
|
|
Packit |
67cb25 |
gsl_linalg_LU_lndet (gsl_matrix * LU)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, n = LU->size1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
double lndet = 0.0;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 0; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
lndet += log (fabs (gsl_matrix_get (LU, i, i)));
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return lndet;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
gsl_linalg_LU_sgndet (gsl_matrix * LU, int signum)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, n = LU->size1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int s = signum;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 0; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
double u = gsl_matrix_get (LU, i, i);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (u < 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
s *= -1;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (u == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
s = 0;
|
|
Packit |
67cb25 |
break;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return s;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
static int
|
|
Packit |
67cb25 |
singular (const gsl_matrix * LU)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, n = LU->size1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 0; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
double u = gsl_matrix_get (LU, i, i);
|
|
Packit |
67cb25 |
if (u == 0) return 1;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return 0;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|