Matt Owen

source code for "files/java/Matrix.java"

return to portfolio
  1.  package lobos.never.die;
  2.  
  3.  import java.util.HashMap;
  4.  
  5.  public class Matrix {
  6.   HashMap <Integer, Double> matrix;
  7.   private int _rows, _cols, _default = 0;
  8.   private double _det;
  9.  
  10.   /* DUMMY ENTRY POINT */
  11.   public static void main(String[] args) {
  12.   Matrix
  13.   a = new Matrix(4, 5,
  14.   1, 1, 1, 1, 0,
  15.   6, 3, -3, -6, 3,
  16.   12, 3, 3, 12, 0,
  17.   8, 1, -1, -8, 0
  18.   );
  19.  
  20.  
  21.   //b.inverse();
  22.  
  23.   /* Output */
  24.   //System.out.println(a.toString(10));
  25.   System.out.println(a.rref().toString(10));
  26.   }
  27.  
  28.   public Matrix(int rows, int cols, double ... vals) {
  29.   int i = 0;
  30.   _rows = rows;
  31.   _cols = cols;
  32.  
  33.   matrix = new HashMap <Integer, Double> (rows*cols/2);
  34.  
  35.   for (double d : vals)
  36.   matrix.put(i++, d);
  37.   }
  38.  
  39.   /* get value at (row, col) */
  40.   public double get(int row, int col) {
  41.   if (!(_rows > row && _cols > col && row > -1 && col > -1))
  42.   throw new ArrayIndexOutOfBoundsException();
  43.  
  44.   if (!matrix.containsKey(_cols * row + col))
  45.   return _default;
  46.  
  47.   return matrix.get(_cols * row + col);
  48.   }
  49.  
  50.   /* set value at (row, col) */
  51.   public void set(int row, int col, double val) {
  52.   if (!(_rows > row && _cols > col && row > -1 && col > -1))
  53.   throw new ArrayIndexOutOfBoundsException();
  54.  
  55.   if (val != _default)
  56.   matrix.put(_cols * row + col, val);
  57.  
  58.   if (val == _default)
  59.   matrix.remove(_cols * row + col);
  60.   }
  61.  
  62.   public void equals(Matrix M) {
  63.   _rows = M._rows;
  64.   _cols = M._cols;
  65.   _default = M._default;
  66.  
  67.   for (int i : M.matrix.keySet())
  68.   matrix.put(i, M.matrix.get(i));
  69.   }
  70.  
  71.   /* addition between two matrices */
  72.   public Matrix add(Matrix r) {
  73.   if (!(_rows == r._rows && _cols == r._cols))
  74.   return new Matrix(0,0);
  75.  
  76.   Matrix M = new Matrix(_rows, _cols);
  77.  
  78.   for (int i = 0; i < _rows; i++)
  79.   for (int j = 0; j < _cols; j++)
  80.   M.set(i, j, get(i, j) + r.get(i,j));
  81.  
  82.   return M;
  83.   }
  84.  
  85.   /* multiplication between two matrices */
  86.   public Matrix multiply(Matrix r) {
  87.   double s = 0;
  88.   Matrix M;
  89.  
  90.   if (_cols != r._rows)
  91.   return new Matrix(0,0);
  92.  
  93.   M = new Matrix(_rows, r._cols);
  94.  
  95.   for (int i = 0; i < _rows; i++)
  96.   for (int j = 0; j < r._cols; j++) {
  97.   s = 0;
  98.   for (int k = 0; k < _cols; k++)
  99.   s += get(i, k)*r.get(k, j);
  100.   M.set(i, j, s);
  101.   }
  102.   return M;
  103.   }
  104.  
  105.   /* get the sub-matrix */
  106.   public Matrix rectangle(int x, int y, int x_len, int y_len) {
  107.   Matrix M = new Matrix(x_len, y_len);
  108.  
  109.   for (int i = x; i < x+x_len; i++)
  110.   for (int j = y; j < y+y_len; j++)
  111.   try {
  112.   M.set(i-x, j-y, get(i, j));
  113.   }
  114.   catch(java.lang.ArrayIndexOutOfBoundsException e) {
  115.   M.set(i-x, j-y, _default);
  116.   }
  117.  
  118.   return M;
  119.   }
  120.  
  121.   /* swap two rows */
  122.   public void swap_row(int r, int s) {
  123.   double swap;
  124.   for (int i=0; i < _cols; i++) {
  125.   swap = get(r, i);
  126.   set(r, i, get(s, i));
  127.   set(s, i, swap);
  128.   }
  129.   }
  130.  
  131.   /* row echelon form */
  132.   public Matrix ref() {
  133.   double d, det = 1;
  134.   Matrix M = rectangle(0, 0, _rows, _cols);
  135.  
  136.   /* get in ref */
  137.   for (int col=0; col < _rows; col++) {
  138.   d = M.get(col, col);
  139.  
  140.   /* scale a non-zero entry in the column */
  141.   if (d != 0) {
  142.   M.scale_row(1/d, col);
  143.   det *= d;
  144.   }
  145.   else
  146.   for (int i=col+1; i < _cols; i++) {
  147.   d = M.get(i, col);
  148.  
  149.   /* swap with the row that has a zero in its pivot point,
  150.   * then scale */
  151.   if (d != 0) {
  152.   M.scale_row(1/d, i);
  153.   M.swap_row(i, col);
  154.   det *= d;
  155.   break;
  156.   }
  157.   }
  158.  
  159.  
  160.   /* eliminate entries besides the pivot point */
  161.   for (int i=col+1; i < _rows; i++) {
  162.   d = M.get(i, col);
  163.   if (d != 0) {
  164.   M.scale_row(-1/d, i);
  165.   M.add_rows(col, i);
  166.   det *= -d;
  167.   }
  168.   }
  169.   }
  170.  
  171.   /* finish computing determinant */
  172.   for (int i=0; i < _rows; i++)
  173.   det *= M.get(i, i);
  174.  
  175.   _det = det;
  176.  
  177.   return M;
  178.   }
  179.  
  180.   /* row-reduced echelon form */
  181.   public Matrix rref() {
  182.   /* */
  183.   double d;
  184.   Matrix M = ref();
  185.  
  186.   for (int i=_rows-1; i > -1; i--) {
  187.   for (int k=0; k < i; k++) {
  188.   d = M.get(k, i);
  189.   if (d != 0)
  190.   M.add_scale(i, k, -d);
  191.   }
  192.   }
  193.   return M;
  194.   }
  195.  
  196.   /* get the inverse of the matrix */
  197.   public Matrix inverse() {
  198.   Matrix M = rectangle(0, 0, _rows, 2*_cols);
  199.  
  200.   for (int i=0; i < _rows; i++)
  201.   M.set(i, i+_cols, 1);
  202.  
  203.   M = M.rref();
  204.  
  205.   return M.rectangle(0, _cols, _rows, _cols);
  206.   }
  207.  
  208.   /* scale row */
  209.   public void scale_row(double d, int row) {
  210.   for (int i=0; i < _cols; i++)
  211.   set(row, i, get(row, i)*d);
  212.   }
  213.  
  214.   /* add rows */
  215.   public void add_scale(int r, int s, double d) {
  216.   for (int i=0; i < _cols; i++)
  217.   set(s, i, d * get(r, i) + get(s, i));
  218.   }
  219.  
  220.   /* add and scale */
  221.   public void add_rows(int r, int s) {
  222.   add_scale(r, s, 1);
  223.   }
  224.  
  225.   /* determinant */
  226.   public double det() {
  227.   ref();
  228.   return _det;
  229.   }
  230.  
  231.   /* */
  232.   public double inf_norm() {
  233.   double m = 0, d = 0;
  234.  
  235.   for (int i=0; i < _rows; i++) {
  236.   m = d > m ? d : m;
  237.   d = 0;
  238.   for (int j=0; j < _cols; j++)
  239.   d = d > get(i, j) ? d : get(i, j);
  240.   }
  241.  
  242.   return m;
  243.   }
  244.  
  245.   /* spill for debugging */
  246.   public String toString(int padding) {
  247.   int x, y;
  248.   String d, s = "";
  249.  
  250.   for (int i = 0; i < _rows * _cols; i++) {
  251.   y = i/_cols;
  252.   x = i%_cols;
  253.  
  254.   d = Double.toString(get(y, x));
  255.  
  256.   /* stupid string repeat */
  257.   for (int k=0; k < padding - d.length(); k++)
  258.   s += " ";
  259.  
  260.   s += d;
  261.  
  262.   if (x == _cols - 1)
  263.   s += "\n";
  264.   }
  265.  
  266.   return s;
  267.   }
  268.  }