RSS

Tag Archives: Linear Algebra

Apache Commons DecompositionSolvers

Apache Commons DecompositionSolvers

Jesus it’s been too long since I got back to this!

Anyway, right, the

DecompositionSolver

Intro / Why-I-Need-To-Worry-About-This

Linear algebra exists for a reason; namely, us. Suppose we’re attempting to find the coordinate values, which under a certain transform, become a specific value. Let’s keep it simple and call it:

 x + 2y + 3z = 1
2x + 4y + 3z = 2
4x           = 3

As I’m sure you can remember from grade school, you have the same number of equations as unknowns, so it is almost certainly solvable. We just subtract two of the first equation from the second, four of the first equation form the third, four of the second from the third, one of the second from the first, and a quarter of the third from the first. Then we maybe divide the third by eight and the second by three, and presto,

x = 3/4
y = 1/8
z = 0

Unfortunately, as programmers, we both know that this is much easier done in practice than in theory; and when you’re automating  a task, a working theory is the only thing that really counts.

So, those of you who have already taken linear algebra (quite possibly all of you) may be familiar with a much easier way of representing this problem:

┌1 2 3┐┌x┐   ┌1┐
│2 4 3││y│ = │2│
└4 0 0┘└z┘   └3┘

A decomposition basically solves this, through a sequence of steps on both sides that reduces the original matrix to an identity matrix, while having the right-hand matrix undergo the same operations. This is commonly written as an augmented matrix, like so:

┌1 2 3│1┐
│2 4 3│2│
└4 0 0│3┘

Matrix reduction is a heck of a lot more straightforward than the nonsense I spouted a few paragraphs back, though going into its details is a bit off topic here. Our final matrix, after the reduction, looks like this:

┌1 0 0│3/4┐
│0 1 0│1/8│
└0 0 1│ 0 ┘

How Do We Do This in Java?

Not just Java, actually; this is specifically about the Apache Commons Math3 decomposition solver interface.

One of the tricks with reduction is that there are a lot of different, equally effective, ways to go about it; and like any other algorithm, the efficiency depends, in large part, on the initial state of your matrix. My personal favorite is the LU Decomposition. (Or, if you prefer a link that isn’t a video, look here.)

First I recommend making a Maven project out of your Java project, presuming that it isn’t already fitting that form factor. Afterwards, open up pom.xml, and add this:

<dependencies>
    <dependency>
        <groupId>org.apache.commons</groupId>
        <artifactId>commons-math3</artifactId>
        <version>3.5</version>
    </dependency>
</dependencies>

right after the close of the build tag. Your project is now pulling classes from across the internet, on Apache Commons Math3. Later on, you may want the version number to be a bit higher; for now I’m using version 3.5.

So, you’ll note that you have access to a host of new classes, all in some subpackage of org.apache.commons.math3. Import org.apache.commons.math3.linear.* into your class file.

We can solve the above problem by creating a RealMatrix of the initial matrix, potentially like so:

RealMatrix matrix = new Array2DRowRealMatrix(new double[][]{
    {1.0, 2.0, 3.0},
    {2.0, 4.0, 3.0},
    {4.0, 0.0, 0.0}
});

But don’t get me wrong, there are literally dozens of ways to create a RealMatrix.

Next, create a RealVector, describing the other side of the equation, perhaps like so:

RealVector vector = new ArrayRealVector(new double[]{
    1.0,
    2.0,
    3.0
});

We now have a matrix and vector representation of the two sides of our equation.

Working with RealMatrix and RealVector

If you’re an experienced programmer, you probably expect some kind of Command Pattern to show up next. It’s certainly what I would do, if I needed to duplicated the exact operations in the exact order on more than one piece of base data. Fortunately, something like it has already been implemented by Apache.

If you look up the Apache Commons Math3 javadocs, you’ll notice that while RealMatrix has a lot of handy operations, they generally just involve polling for data, not actually operating on it. Commons has made the wise move to encapsulate operations in their own classes, rather than just their own methods. There are many dozen other classes, such as MatrixUtils (remember that one!), which both generate and operate on RealMatrix and RealVector classes.

In this instance, turn to DecompositionSolver. It’s meant for tasks just like our own, and there are many subclasses. As I said, my preference is LUDecomposition, but that is only capable of handling square matrices. Since our matrix is square, that’s fine; in other cases when your matrix doesn’t fit the profile, look through EigenDecomposition, SingularValueDecomposition, or some other utility.

For LUDecomposition, we’ll want to do something like this:

DecompositionSolver solver = new LUDecomposition(matrix).getSolver();

The work has been done, as one initialization, LUDecomposition doesn’t just store the matrix as a property; it determines from it the exact sequence of operations necessary to turn it into an identity matrix.

Once you have your solver, you can get your final right-hand vector via:

solver.solve(vector);

which will provide you with:

┌3/4┐
│1/8│
└ 0 ┘

Final Source Code

Here’s a working example of how such a program might work.

 package oberlin.math3;

import java.io.*;
import java.util.*;

import org.apache.commons.math3.linear.*;

public class MatrixReducer {
    
    public static void main(String...args) {
        new MatrixReducer();
    }
    
    public MatrixReducer() {
        try(BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
                Scanner scanner = new Scanner(System.in)) {
            writer.write("\nEnter first row of three numbers: ");
            writer.flush();
            
            RealVector vector1 = new ArrayRealVector(new double[]{scanner.nextDouble(), scanner.nextDouble(), scanner.nextDouble()});
            
            writer.write("\nEnter second row of three numbers: ");
            writer.flush();
            
            RealVector vector2 = new ArrayRealVector(new double[]{scanner.nextDouble(), scanner.nextDouble(), scanner.nextDouble()});

            writer.write("\nEnter third row of three numbers: ");
            writer.flush();
            
            RealVector vector3 = new ArrayRealVector(new double[]{scanner.nextDouble(), scanner.nextDouble(), scanner.nextDouble()});
            
            
            //create matrix
            RealMatrix matrix = MatrixUtils.createRealIdentityMatrix(3);
            matrix.setRowVector(0, vector1);
            matrix.setRowVector(1, vector2);
            matrix.setRowVector(2, vector3);
            
            //get other side
            writer.write("\nEnter vector on right side (3 entries):");
            writer.flush();
            
            RealVector vector = new ArrayRealVector(new double[]{scanner.nextDouble(), scanner.nextDouble(), scanner.nextDouble()});
            
            
            writer.write("Solving...");
            writer.flush();
            
            DecompositionSolver solver = new LUDecomposition(matrix).getSolver();
            matrix = solver.solve(matrix);
            vector = solver.solve(vector);
            
            writer.write("Solution: \n");
            writer.flush();
            
            writer.write("┌" + matrix.getEntry(0, 0) + " " + matrix.getEntry(0, 1) + " "
                    + matrix.getEntry(0, 2) + "┐┌x┐   ┌" + Double.toString(vector.getEntry(0)) + "┐\n");
            writer.write("│" + matrix.getEntry(1, 0) + " " + matrix.getEntry(1, 1) + " "
                    + matrix.getEntry(1, 2) + "││y│ = │" + Double.toString(vector.getEntry(1)) + "│\n");
            writer.write("└" + matrix.getEntry(2, 0) + " " + matrix.getEntry(2, 1) + " "
                    + matrix.getEntry(2, 2) + "┘└z┘   └" + Double.toString(vector.getEntry(2)) + "┘\n");
            
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
Advertisements
 
Leave a comment

Posted by on June 30, 2015 in Java, Programming

 

Tags: , , , , , , , , , ,