CODEWITHSUNDEEP
javadebuggingmatrixlinear-algebraojalgo
Nick Simos
Nick Simos

Reputation: 67

Debugging: Unusual runtime in linear algebra calculations using Java, ojalgo

I have a moderately large Ax = b problem that I want to solve. Matrix A is 600x600.

My code solves the problem, but takes unusually long time to do so. So, I tried to check (with System.currentTimeMillis()) to see where my code slows down.

It turns out, that during the calculations of A, I execute the command A = L1 * A0 * L1.transpose(). The process consumes almost 100% of its total time in this line.

A weird thing is, L1 is a 600x600 unit matrix (that is, A[i,j] = 1, if i == j and 0, otherwise). So, this line should not really take that long to execute. It should also be easy to bypass in this problem

An even weirder thing though, happens if I try to bypass that line by commenting it out and replacing it with A = A0. Then the code takes way too long (after 10x the original time I killed it) to execute. Also, the CPU usage reaches 100%.

I checked, and it turns out that A and L1 * A0 * L1.transpose() are identical.

To sum up, using a part of my Java code (I use library ojalgo for handling matrices):

// PrimitiveMatrix A0, L1, b are already calculated.

long startTime = System.currentTimeMillis();
System.out.println((System.currentTimeMillis() - startTime0) / 1000.0); // this prints about 2 seconds, concerning calculations of A0, L1, b.

PrimitiveMatrix A = L1.multiply(A0).multiply((L1).transpose());
System.out.println((System.currentTimeMillis() - startTime0) / 1000.0);  // this prints about 67 seconds    

// PrimitiveMatrix A = A0; // if this is NOT a comment, then the code has not run after (10+)x my "normal" time 

final PrimitiveMatrix x = (A.invert()).multiply(b);

System.out.println((System.currentTimeMillis() - startTime0) / 1000.0);  // this prints about 69 seconds  

// I checked that
// A0.equals(L1.multiply(A0).multiply((L1).transpose())
// returns true

This whole process takes about 69 seconds, and 65 of them are consumed in a trivial calculation, that I have failed to bypass. The same procedure has run successfully in the past for smaller matrices (60x60).

I am not really sure how to proceed with my debugging attempts. Any help would be greatly appreciated.

It seems the problem runs a little deeper than I had originally estimated. I tried to print those matrices in order to upload them, but then another problem appeared. I found out that my code crashes the very first time I run System.out.println(A0.get(aRow,aColumn));. A0 was created by adding numbers of type double to every position of a zero matrix with dimensions 600x600. In addition, the following messages appear:

       Exception in thread "main" java.lang.StackOverflowError
    at org.ojalgo.matrix.store.SuperimposedStore.get(SuperimposedStore.java:84)
    at org.ojalgo.matrix.store.SuperimposedStore.get(SuperimposedStore.java:84)
    at org.ojalgo.matrix.store.SuperimposedStore.get(SuperimposedStore.java:84)
...

Again, I want to emphasize that the same process runs normally when those matrices are 60x60.

Upvotes: 1

Views: 200

Answers (1)

apete
apete

Reputation: 1320

I assume you're using BasicMatrix#add(int,int,Number)

Did you call that method 600x600 times to build your matrix? You should NOT do that!

In newer versions of ojAlgo that method has been removed because it was often misunderstood/misused.

You should read this: https://github.com/optimatika/ojAlgo/wiki/Getting-Started

Upvotes: 2

Related Questions