[JAVA3D] vecmath's LU decomposition and backsolve are SLOW

[Doug James]

Hello All

The vecmath.GMatrix.LUD method appears to take longer than
necessary, e.g., it appears worse than O(n^3) for an n-by-n
matrix. But worse, the vecmath.GVector.LUBackSolve takes
longer than the LU decomposition for large n !?! The back solve
should be O(n^2) and very fast. The output of my test code
produces timings as follows for an n-by-n matrix, running on
an Ultra-60 (although the problem occurs in Windows
implementations, too):

n=200
        LUD:          348 ms.
        LUDBackSolve: 486 ms.
n=400
        LUD:          4000 ms.
        LUDBackSolve: 6127 ms.
n=800
        LUD:          48733 ms.
        LUDBackSolve: 73751 ms.

So, roughly, each doubling introduces a factor of ~12.1 so that
the scaling is ~C*n^3.6 -- very bad. But the fact that the
LUDBackSolve is worse than the LUD defeats the purpose of using
this LU code.

Also, it would be nice to see the LU implementation optionally take
advantage of the fact that LU may be done in-place on a matrix
without having to allocate extra memory.

Hope I'm not missing something,
Doug James


java -version
java version "1.2"
Classic VM (build JDK-1.2-V, green threads, sunwjit)

java -fullversion
java full version "JDK-1.2-V"


Code follows:


import javax.vecmath.*;
public class BadComplexity {
    public static void main(String[] args) {
        int n = 1;
        if(args.length > 0) n = Integer.parseInt(args[0]);
        simpleTestVecmathLU(n);
    }
    public static void simpleTestVecmathLU(int n) {

        //// Construct matrices for A*x=LU*x=b system:
        GMatrix LU = new GMatrix(n,n);
        GMatrix A  = new GMatrix(n,n);
        GVector x  = new GVector(n);
        GVector b  = new GVector(n);
        GVector permutation = new GVector(n);

        //// Set A & b to be random matrices:

        java.util.Random   R = new java.util.Random();
        for(int i=0; i<n; i++) {
            b.setElement(i,R.nextDouble());
            for(int j=0; j<n; j++)
                A.setElement(i,j,R.nextDouble());
        }

        //// Timing of LUD and LUDBackSolve:
        long tStart,tStop;

        tStart = System.currentTimeMillis();
        A.LUD(LU,permutation);
        tStop  = System.currentTimeMillis();
        System.out.println("LUD:          "+(tStop-tStart)+" ms.");

        tStart = System.currentTimeMillis();
        x.LUDBackSolve(LU,b,permutation);
        tStop  = System.currentTimeMillis();
        System.out.println("LUDBackSolve: "+(tStop-tStart)+" ms.");
    }
}

-------------------------------------
Doug James
Institute of Applied Mathematics
University of British Columbia
[EMAIL PROTECTED]
-------------------------------------

===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST".  For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".