Merge branch 'releases/Release_2_10_2b1_Branch'
[jalview.git] / src / jalview / math / Matrix.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.math;
22
23 import jalview.util.Format;
24 import jalview.util.MessageManager;
25
26 import java.io.PrintStream;
27
28 /**
29  * A class to model rectangular matrices of double values and operations on them
30  */
31 public class Matrix implements MatrixI
32 {
33   /*
34    * the cell values in row-major order
35    */
36   private double[][] value;
37
38   /*
39    * the number of rows
40    */
41   protected int rows;
42
43   /*
44    * the number of columns
45    */
46   protected int cols;
47
48   protected double[] d; // Diagonal
49
50   protected double[] e; // off diagonal
51
52   /**
53    * maximum number of iterations for tqli
54    * 
55    */
56   private static final int maxIter = 45; // fudge - add 15 iterations, just in
57                                          // case
58
59   /**
60    * Default constructor
61    */
62   public Matrix()
63   {
64
65   }
66
67   /**
68    * Creates a new Matrix object containing a copy of the supplied array values.
69    * For example
70    * 
71    * <pre>
72    *   new Matrix(new double[][] {{2, 3, 4}, {5, 6, 7})
73    * constructs
74    *   (2 3 4)
75    *   (5 6 7)
76    * </pre>
77    * 
78    * Note that ragged arrays (with not all rows, or columns, of the same
79    * length), are not supported by this class. They can be constructed, but
80    * results of operations on them are undefined and may throw exceptions.
81    * 
82    * @param values
83    *          the matrix values in row-major order
84    */
85   public Matrix(double[][] values)
86   {
87     this.rows = values.length;
88     this.cols = this.rows == 0 ? 0 : values[0].length;
89
90     /*
91      * make a copy of the values array, for immutability
92      */
93     this.value = new double[rows][];
94     int i = 0;
95     for (double[] row : values)
96     {
97       if (row != null)
98       {
99         value[i] = new double[row.length];
100         System.arraycopy(row, 0, value[i], 0, row.length);
101       }
102       i++;
103     }
104   }
105
106   /**
107    * Returns a new matrix which is the transpose of this one
108    * 
109    * @return
110    */
111   @Override
112   public MatrixI transpose()
113   {
114     double[][] out = new double[cols][rows];
115
116     for (int i = 0; i < cols; i++)
117     {
118       for (int j = 0; j < rows; j++)
119       {
120         out[i][j] = value[j][i];
121       }
122     }
123
124     return new Matrix(out);
125   }
126
127   /**
128    * DOCUMENT ME!
129    * 
130    * @param ps
131    *          DOCUMENT ME!
132    * @param format
133    */
134   @Override
135   public void print(PrintStream ps, String format)
136   {
137     for (int i = 0; i < rows; i++)
138     {
139       for (int j = 0; j < cols; j++)
140       {
141         Format.print(ps, format, getValue(i, j));
142       }
143
144       ps.println();
145     }
146   }
147
148   /**
149    * Returns a new matrix which is the result of premultiplying this matrix by
150    * the supplied argument. If this of size AxB (A rows and B columns), and the
151    * argument is CxA (C rows and A columns), the result is of size CxB.
152    * 
153    * @param in
154    * 
155    * @return
156    * @throws IllegalArgumentException
157    *           if the number of columns in the pre-multiplier is not equal to
158    *           the number of rows in the multiplicand (this)
159    */
160   @Override
161   public MatrixI preMultiply(MatrixI in)
162   {
163     if (in.width() != rows)
164     {
165       throw new IllegalArgumentException("Can't pre-multiply " + this.rows
166               + " rows by " + in.width() + " columns");
167     }
168     double[][] tmp = new double[in.height()][this.cols];
169
170     for (int i = 0; i < in.height(); i++)
171     {
172       for (int j = 0; j < this.cols; j++)
173       {
174         /*
175          * result[i][j] is the vector product of 
176          * in.row[i] and this.column[j]
177          */
178         for (int k = 0; k < in.width(); k++)
179         {
180           tmp[i][j] += (in.getValue(i, k) * this.value[k][j]);
181         }
182       }
183     }
184
185     return new Matrix(tmp);
186   }
187
188   /**
189    * 
190    * @param in
191    * 
192    * @return
193    */
194   public double[] vectorPostMultiply(double[] in)
195   {
196     double[] out = new double[in.length];
197
198     for (int i = 0; i < in.length; i++)
199     {
200       out[i] = 0.0;
201
202       for (int k = 0; k < in.length; k++)
203       {
204         out[i] += (value[i][k] * in[k]);
205       }
206     }
207
208     return out;
209   }
210
211   /**
212    * Returns a new matrix which is the result of postmultiplying this matrix by
213    * the supplied argument. If this of size AxB (A rows and B columns), and the
214    * argument is BxC (B rows and C columns), the result is of size AxC.
215    * <p>
216    * This method simply returns the result of in.preMultiply(this)
217    * 
218    * @param in
219    * 
220    * @return
221    * @throws IllegalArgumentException
222    *           if the number of rows in the post-multiplier is not equal to the
223    *           number of columns in the multiplicand (this)
224    * @see #preMultiply(Matrix)
225    */
226   @Override
227   public MatrixI postMultiply(MatrixI in)
228   {
229     if (in.height() != this.cols)
230     {
231       throw new IllegalArgumentException("Can't post-multiply " + this.cols
232               + " columns by " + in.height() + " rows");
233     }
234     return in.preMultiply(this);
235   }
236
237   /**
238    * Answers a new matrix with a copy of the values in this one
239    * 
240    * @return
241    */
242   @Override
243   public MatrixI copy()
244   {
245     double[][] newmat = new double[rows][cols];
246
247     for (int i = 0; i < rows; i++)
248     {
249       System.arraycopy(value[i], 0, newmat[i], 0, value[i].length);
250     }
251
252     return new Matrix(newmat);
253   }
254
255   /**
256    * DOCUMENT ME!
257    */
258   @Override
259   public void tred()
260   {
261     int n = rows;
262     int k;
263     int j;
264     int i;
265
266     double scale;
267     double hh;
268     double h;
269     double g;
270     double f;
271
272     this.d = new double[rows];
273     this.e = new double[rows];
274
275     for (i = n; i >= 2; i--)
276     {
277       final int l = i - 1;
278       h = 0.0;
279       scale = 0.0;
280
281       if (l > 1)
282       {
283         for (k = 1; k <= l; k++)
284         {
285           double v = Math.abs(getValue(i - 1, k - 1));
286           scale += v;
287         }
288
289         if (scale == 0.0)
290         {
291           e[i - 1] = getValue(i - 1, l - 1);
292         }
293         else
294         {
295           for (k = 1; k <= l; k++)
296           {
297             double v = divideValue(i - 1, k - 1, scale);
298             h += v * v;
299           }
300
301           f = getValue(i - 1, l - 1);
302
303           if (f > 0)
304           {
305             g = -1.0 * Math.sqrt(h);
306           }
307           else
308           {
309             g = Math.sqrt(h);
310           }
311
312           e[i - 1] = scale * g;
313           h -= (f * g);
314           setValue(i - 1, l - 1, f - g);
315           f = 0.0;
316
317           for (j = 1; j <= l; j++)
318           {
319             double val = getValue(i - 1, j - 1) / h;
320             setValue(j - 1, i - 1, val);
321             g = 0.0;
322
323             for (k = 1; k <= j; k++)
324             {
325               g += (getValue(j - 1, k - 1) * getValue(i - 1, k - 1));
326             }
327
328             for (k = j + 1; k <= l; k++)
329             {
330               g += (getValue(k - 1, j - 1) * getValue(i - 1, k - 1));
331             }
332
333             e[j - 1] = g / h;
334             f += (e[j - 1] * getValue(i - 1, j - 1));
335           }
336
337           hh = f / (h + h);
338
339           for (j = 1; j <= l; j++)
340           {
341             f = getValue(i - 1, j - 1);
342             g = e[j - 1] - (hh * f);
343             e[j - 1] = g;
344
345             for (k = 1; k <= j; k++)
346             {
347               double val = (f * e[k - 1]) + (g * getValue(i - 1, k - 1));
348               addValue(j - 1, k - 1, -val);
349             }
350           }
351         }
352       }
353       else
354       {
355         e[i - 1] = getValue(i - 1, l - 1);
356       }
357
358       d[i - 1] = h;
359     }
360
361     d[0] = 0.0;
362     e[0] = 0.0;
363
364     for (i = 1; i <= n; i++)
365     {
366       final int l = i - 1;
367
368       if (d[i - 1] != 0.0)
369       {
370         for (j = 1; j <= l; j++)
371         {
372           g = 0.0;
373
374           for (k = 1; k <= l; k++)
375           {
376             g += (getValue(i - 1, k - 1) * getValue(k - 1, j - 1));
377           }
378
379           for (k = 1; k <= l; k++)
380           {
381             addValue(k - 1, j - 1, -(g * getValue(k - 1, i - 1)));
382           }
383         }
384       }
385
386       d[i - 1] = getValue(i - 1, i - 1);
387       setValue(i - 1, i - 1, 1.0);
388
389       for (j = 1; j <= l; j++)
390       {
391         setValue(j - 1, i - 1, 0.0);
392         setValue(i - 1, j - 1, 0.0);
393       }
394     }
395   }
396
397   /**
398    * Adds f to the value at [i, j] and returns the new value
399    * 
400    * @param i
401    * @param j
402    * @param f
403    */
404   protected double addValue(int i, int j, double f)
405   {
406     double v = value[i][j] + f;
407     value[i][j] = v;
408     return v;
409   }
410
411   /**
412    * Divides the value at [i, j] by divisor and returns the new value. If d is
413    * zero, returns the unchanged value.
414    * 
415    * @param i
416    * @param j
417    * @param divisor
418    * @return
419    */
420   protected double divideValue(int i, int j, double divisor)
421   {
422     if (divisor == 0d)
423     {
424       return getValue(i, j);
425     }
426     double v = value[i][j];
427     v = v / divisor;
428     value[i][j] = v;
429     return v;
430   }
431
432   /**
433    * DOCUMENT ME!
434    */
435   @Override
436   public void tqli() throws Exception
437   {
438     int n = rows;
439
440     int m;
441     int l;
442     int iter;
443     int i;
444     int k;
445     double s;
446     double r;
447     double p;
448
449     double g;
450     double f;
451     double dd;
452     double c;
453     double b;
454
455     for (i = 2; i <= n; i++)
456     {
457       e[i - 2] = e[i - 1];
458     }
459
460     e[n - 1] = 0.0;
461
462     for (l = 1; l <= n; l++)
463     {
464       iter = 0;
465
466       do
467       {
468         for (m = l; m <= (n - 1); m++)
469         {
470           dd = Math.abs(d[m - 1]) + Math.abs(d[m]);
471
472           if ((Math.abs(e[m - 1]) + dd) == dd)
473           {
474             break;
475           }
476         }
477
478         if (m != l)
479         {
480           iter++;
481
482           if (iter == maxIter)
483           {
484             throw new Exception(MessageManager.formatMessage(
485                     "exception.matrix_too_many_iteration", new String[]
486                     { "tqli", Integer.valueOf(maxIter).toString() }));
487           }
488           else
489           {
490             // System.out.println("Iteration " + iter);
491           }
492
493           g = (d[l] - d[l - 1]) / (2.0 * e[l - 1]);
494           r = Math.sqrt((g * g) + 1.0);
495           g = d[m - 1] - d[l - 1] + (e[l - 1] / (g + sign(r, g)));
496           c = 1.0;
497           s = c;
498           p = 0.0;
499
500           for (i = m - 1; i >= l; i--)
501           {
502             f = s * e[i - 1];
503             b = c * e[i - 1];
504
505             if (Math.abs(f) >= Math.abs(g))
506             {
507               c = g / f;
508               r = Math.sqrt((c * c) + 1.0);
509               e[i] = f * r;
510               s = 1.0 / r;
511               c *= s;
512             }
513             else
514             {
515               s = f / g;
516               r = Math.sqrt((s * s) + 1.0);
517               e[i] = g * r;
518               c = 1.0 / r;
519               s *= c;
520             }
521
522             g = d[i] - p;
523             r = ((d[i - 1] - g) * s) + (2.0 * c * b);
524             p = s * r;
525             d[i] = g + p;
526             g = (c * r) - b;
527
528             for (k = 1; k <= n; k++)
529             {
530               f = getValue(k - 1, i);
531               setValue(k - 1, i, (s * getValue(k - 1, i - 1)) + (c * f));
532               setValue(k - 1, i - 1,
533                       (c * getValue(k - 1, i - 1)) - (s * f));
534             }
535           }
536
537           d[l - 1] = d[l - 1] - p;
538           e[l - 1] = g;
539           e[m - 1] = 0.0;
540         }
541       } while (m != l);
542     }
543   }
544
545   @Override
546   public double getValue(int i, int j)
547   {
548     return value[i][j];
549   }
550
551   @Override
552   public void setValue(int i, int j, double val)
553   {
554     value[i][j] = val;
555   }
556
557   /**
558    * DOCUMENT ME!
559    */
560   public void tred2()
561   {
562     int n = rows;
563     int l;
564     int k;
565     int j;
566     int i;
567
568     double scale;
569     double hh;
570     double h;
571     double g;
572     double f;
573
574     this.d = new double[rows];
575     this.e = new double[rows];
576
577     for (i = n - 1; i >= 1; i--)
578     {
579       l = i - 1;
580       h = 0.0;
581       scale = 0.0;
582
583       if (l > 0)
584       {
585         for (k = 0; k < l; k++)
586         {
587           scale += Math.abs(value[i][k]);
588         }
589
590         if (scale == 0.0)
591         {
592           e[i] = value[i][l];
593         }
594         else
595         {
596           for (k = 0; k < l; k++)
597           {
598             value[i][k] /= scale;
599             h += (value[i][k] * value[i][k]);
600           }
601
602           f = value[i][l];
603
604           if (f > 0)
605           {
606             g = -1.0 * Math.sqrt(h);
607           }
608           else
609           {
610             g = Math.sqrt(h);
611           }
612
613           e[i] = scale * g;
614           h -= (f * g);
615           value[i][l] = f - g;
616           f = 0.0;
617
618           for (j = 0; j < l; j++)
619           {
620             value[j][i] = value[i][j] / h;
621             g = 0.0;
622
623             for (k = 0; k < j; k++)
624             {
625               g += (value[j][k] * value[i][k]);
626             }
627
628             for (k = j; k < l; k++)
629             {
630               g += (value[k][j] * value[i][k]);
631             }
632
633             e[j] = g / h;
634             f += (e[j] * value[i][j]);
635           }
636
637           hh = f / (h + h);
638
639           for (j = 0; j < l; j++)
640           {
641             f = value[i][j];
642             g = e[j] - (hh * f);
643             e[j] = g;
644
645             for (k = 0; k < j; k++)
646             {
647               value[j][k] -= ((f * e[k]) + (g * value[i][k]));
648             }
649           }
650         }
651       }
652       else
653       {
654         e[i] = value[i][l];
655       }
656
657       d[i] = h;
658     }
659
660     d[0] = 0.0;
661     e[0] = 0.0;
662
663     for (i = 0; i < n; i++)
664     {
665       l = i - 1;
666
667       if (d[i] != 0.0)
668       {
669         for (j = 0; j < l; j++)
670         {
671           g = 0.0;
672
673           for (k = 0; k < l; k++)
674           {
675             g += (value[i][k] * value[k][j]);
676           }
677
678           for (k = 0; k < l; k++)
679           {
680             value[k][j] -= (g * value[k][i]);
681           }
682         }
683       }
684
685       d[i] = value[i][i];
686       value[i][i] = 1.0;
687
688       for (j = 0; j < l; j++)
689       {
690         value[j][i] = 0.0;
691         value[i][j] = 0.0;
692       }
693     }
694   }
695
696   /**
697    * DOCUMENT ME!
698    */
699   public void tqli2() throws Exception
700   {
701     int n = rows;
702
703     int m;
704     int l;
705     int iter;
706     int i;
707     int k;
708     double s;
709     double r;
710     double p;
711     ;
712
713     double g;
714     double f;
715     double dd;
716     double c;
717     double b;
718
719     for (i = 2; i <= n; i++)
720     {
721       e[i - 2] = e[i - 1];
722     }
723
724     e[n - 1] = 0.0;
725
726     for (l = 1; l <= n; l++)
727     {
728       iter = 0;
729
730       do
731       {
732         for (m = l; m <= (n - 1); m++)
733         {
734           dd = Math.abs(d[m - 1]) + Math.abs(d[m]);
735
736           if ((Math.abs(e[m - 1]) + dd) == dd)
737           {
738             break;
739           }
740         }
741
742         if (m != l)
743         {
744           iter++;
745
746           if (iter == maxIter)
747           {
748             throw new Exception(MessageManager.formatMessage(
749                     "exception.matrix_too_many_iteration", new String[]
750                     { "tqli2", Integer.valueOf(maxIter).toString() }));
751           }
752           else
753           {
754             // System.out.println("Iteration " + iter);
755           }
756
757           g = (d[l] - d[l - 1]) / (2.0 * e[l - 1]);
758           r = Math.sqrt((g * g) + 1.0);
759           g = d[m - 1] - d[l - 1] + (e[l - 1] / (g + sign(r, g)));
760           c = 1.0;
761           s = c;
762           p = 0.0;
763
764           for (i = m - 1; i >= l; i--)
765           {
766             f = s * e[i - 1];
767             b = c * e[i - 1];
768
769             if (Math.abs(f) >= Math.abs(g))
770             {
771               c = g / f;
772               r = Math.sqrt((c * c) + 1.0);
773               e[i] = f * r;
774               s = 1.0 / r;
775               c *= s;
776             }
777             else
778             {
779               s = f / g;
780               r = Math.sqrt((s * s) + 1.0);
781               e[i] = g * r;
782               c = 1.0 / r;
783               s *= c;
784             }
785
786             g = d[i] - p;
787             r = ((d[i - 1] - g) * s) + (2.0 * c * b);
788             p = s * r;
789             d[i] = g + p;
790             g = (c * r) - b;
791
792             for (k = 1; k <= n; k++)
793             {
794               f = value[k - 1][i];
795               value[k - 1][i] = (s * value[k - 1][i - 1]) + (c * f);
796               value[k - 1][i - 1] = (c * value[k - 1][i - 1]) - (s * f);
797             }
798           }
799
800           d[l - 1] = d[l - 1] - p;
801           e[l - 1] = g;
802           e[m - 1] = 0.0;
803         }
804       } while (m != l);
805     }
806   }
807
808   /**
809    * Answers the first argument with the sign of the second argument
810    * 
811    * @param a
812    * @param b
813    * 
814    * @return
815    */
816   static double sign(double a, double b)
817   {
818     if (b < 0)
819     {
820       return -Math.abs(a);
821     }
822     else
823     {
824       return Math.abs(a);
825     }
826   }
827
828   /**
829    * Returns an array containing the values in the specified column
830    * 
831    * @param col
832    * 
833    * @return
834    */
835   public double[] getColumn(int col)
836   {
837     double[] out = new double[rows];
838
839     for (int i = 0; i < rows; i++)
840     {
841       out[i] = value[i][col];
842     }
843
844     return out;
845   }
846
847   /**
848    * DOCUMENT ME!
849    * 
850    * @param ps
851    *          DOCUMENT ME!
852    * @param format
853    */
854   @Override
855   public void printD(PrintStream ps, String format)
856   {
857     for (int j = 0; j < rows; j++)
858     {
859       Format.print(ps, format, d[j]);
860     }
861   }
862
863   /**
864    * DOCUMENT ME!
865    * 
866    * @param ps
867    *          DOCUMENT ME!
868    * @param format
869    *          TODO
870    */
871   @Override
872   public void printE(PrintStream ps, String format)
873   {
874     for (int j = 0; j < rows; j++)
875     {
876       Format.print(ps, format, e[j]);
877     }
878   }
879
880   @Override
881   public double[] getD()
882   {
883     return d;
884   }
885
886   @Override
887   public double[] getE()
888   {
889     return e;
890   }
891
892   @Override
893   public int height()
894   {
895     return rows;
896   }
897
898   @Override
899   public int width()
900   {
901     return cols;
902   }
903
904   @Override
905   public double[] getRow(int i)
906   {
907     double[] row = new double[cols];
908     System.arraycopy(value[i], 0, row, 0, cols);
909     return row;
910   }
911
912   /**
913    * Returns a length 2 array of {minValue, maxValue} of all values in the
914    * matrix. Returns null if the matrix is null or empty.
915    * 
916    * @return
917    */
918   double[] findMinMax()
919   {
920     if (value == null)
921     {
922       return null;
923     }
924     double min = Double.MAX_VALUE;
925     double max = -Double.MAX_VALUE;
926     boolean empty = true;
927     for (double[] row : value)
928     {
929       if (row != null)
930       {
931         for (double x : row)
932         {
933           empty = false;
934           if (x > max)
935           {
936             max = x;
937           }
938           if (x < min)
939           {
940             min = x;
941           }
942         }
943       }
944     }
945     return empty ? null : new double[] { min, max };
946   }
947
948   /**
949    * {@inheritDoc}
950    */
951   @Override
952   public void reverseRange(boolean maxToZero)
953   {
954     if (value == null)
955     {
956       return;
957     }
958     double[] minMax = findMinMax();
959     if (minMax == null)
960     {
961       return; // empty matrix
962     }
963     double subtractFrom = maxToZero ? minMax[1] : minMax[0] + minMax[1];
964
965     for (double[] row : value)
966     {
967       if (row != null)
968       {
969         int j = 0;
970         for (double x : row)
971         {
972           row[j] = subtractFrom - x;
973           j++;
974         }
975       }
976     }
977   }
978
979   /**
980    * Multiplies every entry in the matrix by the given value.
981    * 
982    * @param
983    */
984   @Override
985   public void multiply(double by)
986   {
987     for (double[] row : value)
988     {
989       if (row != null)
990       {
991         for (int i = 0; i < row.length; i++)
992         {
993           row[i] *= by;
994         }
995       }
996     }
997   }
998 }