lu.c

Go to the documentation of this file.

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
/*
 * This code was (mostly) written by Ken Turkowski, who said:
 *
 * Oh, that. I wrote it in college the first time. It's open source - I think I
 * posted it after seeing so many people solve equations by inverting matrices
 * by computing minors naïvely.
 * -Ken
 *
 * The views represented here are mine and are not necessarily shared by
 * my employer.
        Ken Turkowski                   turk@apple.com
        Immersive Media Technologist    http://www.worldserver.com/turk/
        Apple Computer, Inc.
        1 Infinite Loop, MS 302-3VR
        Cupertino, CA 95014
 */
 
 
 
/* This module solves linear equations in several variables (Ax = b) using
 * LU decomposition with partial pivoting and row equilibration.  Although
 * slightly more work than Gaussian elimination, it is faster for solving
 * several equations using the same coefficient matrix.  It is
 * particularly useful for matrix inversion, by sequentially solving the
 * equations with the columns of the unit matrix.
 *
 * lu_decompose() decomposes the coefficient matrix into the LU matrix,
 * and lu_solve() solves the series of matrix equations using the
 * previous LU decomposition.
 *
 *      Ken Turkowski (apple!turk)
 *      written 3/2/79, revised and enhanced 8/9/83.
 */
 
#include "config.h"
 
#include <math.h>
#include <neatogen/neato.h>
#include <util/alloc.h>
 
static double *scales;
static double **lu;
static int *ps;
 
/* lu_decompose() decomposes the coefficient matrix A into upper and lower
 * triangular matrices, the composite being the LU matrix.
 *
 * The arguments are:
 *
 *      a - the (n x n) coefficient matrix
 *      n - the order of the matrix
 *
 *  1 is returned if the decomposition was successful,
 *  and 0 is returned if the coefficient matrix is singular.
 */
 
int lu_decompose(double **a, int n)
{
    int i, j, k;
    int pivotindex = 0;
    double pivot, biggest, mult, tempf;
 
    if (lu)
        free_array(lu);
    lu = new_array(n, n, 0.0);
    free(ps);
    ps = gv_calloc(n, sizeof(int));
    free(scales);
    scales = gv_calloc(n, sizeof(double));
 
    for (i = 0; i < n; i++) {   /* For each row */
        /* Find the largest element in each row for row equilibration */
        biggest = 0.0;
        for (j = 0; j < n; j++)
            biggest = fmax(biggest, fabs(lu[i][j] = a[i][j]));
        if (biggest > 0.0)
            scales[i] = 1.0 / biggest;
        else {
            scales[i] = 0.0;
            return 0;           /* Zero row: singular matrix */
        }
        ps[i] = i;              /* Initialize pivot sequence */
    }
 
    for (k = 0; k < n - 1; k++) {       /* For each column */
        /* Find the largest element in each column to pivot around */
        biggest = 0.0;
        for (i = k; i < n; i++) {
            if (biggest < (tempf = fabs(lu[ps[i]][k]) * scales[ps[i]])) {
                biggest = tempf;
                pivotindex = i;
            }
        }
        if (biggest <= 0.0)
            return 0;           /* Zero column: singular matrix */
        if (pivotindex != k) {  /* Update pivot sequence */
            j = ps[k];
            ps[k] = ps[pivotindex];
            ps[pivotindex] = j;
        }
 
        /* Pivot, eliminating an extra variable  each time */
        pivot = lu[ps[k]][k];
        for (i = k + 1; i < n; i++) {
            lu[ps[i]][k] = mult = lu[ps[i]][k] / pivot;
            for (j = k + 1; j < n; j++)
                lu[ps[i]][j] -= mult * lu[ps[k]][j];
        }
    }
 
    if (lu[ps[n - 1]][n - 1] == 0.0)
        return 0;               /* Singular matrix */
    return 1;
}
 
/* lu_solve() solves the linear equation (Ax = b) after the matrix A has
 * been decomposed with lu_decompose() into the lower and upper triangular
 * matrices L and U.
 *
 * The arguments are:
 *
 *      x - the solution vector
 *      b - the constant vector
 *      n - the order of the equation
*/
 
void lu_solve(double *x, double *b, int n)
{
    int i, j;
    double dot;
 
    /* Vector reduction using U triangular matrix */
    for (i = 0; i < n; i++) {
        dot = 0.0;
        for (j = 0; j < i; j++)
            dot += lu[ps[i]][j] * x[j];
        x[i] = b[ps[i]] - dot;
    }
 
    /* Back substitution, in L triangular matrix */
    for (i = n - 1; i >= 0; i--) {
        dot = 0.0;
        for (j = i + 1; j < n; j++)
            dot += lu[ps[i]][j] * x[j];
        x[i] = (x[i] - dot) / lu[ps[i]][i];
    }
}