Merge branch 'features/JAL-2446NCList' into features/JAL-2574findFeaturesByColumn
[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, (c * getValue(k - 1, i - 1)) - (s * f));
533             }
534           }
535
536           d[l - 1] = d[l - 1] - p;
537           e[l - 1] = g;
538           e[m - 1] = 0.0;
539         }
540       } while (m != l);
541     }
542   }
543
544   @Override
545   public double getValue(int i, int j)
546   {
547     return value[i][j];
548   }
549
550   @Override
551   public void setValue(int i, int j, double val)
552   {
553     value[i][j] = val;
554   }
555
556   /**
557    * DOCUMENT ME!
558    */
559   public void tred2()
560   {
561     int n = rows;
562     int l;
563     int k;
564     int j;
565     int i;
566
567     double scale;
568     double hh;
569     double h;
570     double g;
571     double f;
572
573     this.d = new double[rows];
574     this.e = new double[rows];
575
576     for (i = n - 1; i >= 1; i--)
577     {
578       l = i - 1;
579       h = 0.0;
580       scale = 0.0;
581
582       if (l > 0)
583       {
584         for (k = 0; k < l; k++)
585         {
586           scale += Math.abs(value[i][k]);
587         }
588
589         if (scale == 0.0)
590         {
591           e[i] = value[i][l];
592         }
593         else
594         {
595           for (k = 0; k < l; k++)
596           {
597             value[i][k] /= scale;
598             h += (value[i][k] * value[i][k]);
599           }
600
601           f = value[i][l];
602
603           if (f > 0)
604           {
605             g = -1.0 * Math.sqrt(h);
606           }
607           else
608           {
609             g = Math.sqrt(h);
610           }
611
612           e[i] = scale * g;
613           h -= (f * g);
614           value[i][l] = f - g;
615           f = 0.0;
616
617           for (j = 0; j < l; j++)
618           {
619             value[j][i] = value[i][j] / h;
620             g = 0.0;
621
622             for (k = 0; k < j; k++)
623             {
624               g += (value[j][k] * value[i][k]);
625             }
626
627             for (k = j; k < l; k++)
628             {
629               g += (value[k][j] * value[i][k]);
630             }
631
632             e[j] = g / h;
633             f += (e[j] * value[i][j]);
634           }
635
636           hh = f / (h + h);
637
638           for (j = 0; j < l; j++)
639           {
640             f = value[i][j];
641             g = e[j] - (hh * f);
642             e[j] = g;
643
644             for (k = 0; k < j; k++)
645             {
646               value[j][k] -= ((f * e[k]) + (g * value[i][k]));
647             }
648           }
649         }
650       }
651       else
652       {
653         e[i] = value[i][l];
654       }
655
656       d[i] = h;
657     }
658
659     d[0] = 0.0;
660     e[0] = 0.0;
661
662     for (i = 0; i < n; i++)
663     {
664       l = i - 1;
665
666       if (d[i] != 0.0)
667       {
668         for (j = 0; j < l; j++)
669         {
670           g = 0.0;
671
672           for (k = 0; k < l; k++)
673           {
674             g += (value[i][k] * value[k][j]);
675           }
676
677           for (k = 0; k < l; k++)
678           {
679             value[k][j] -= (g * value[k][i]);
680           }
681         }
682       }
683
684       d[i] = value[i][i];
685       value[i][i] = 1.0;
686
687       for (j = 0; j < l; j++)
688       {
689         value[j][i] = 0.0;
690         value[i][j] = 0.0;
691       }
692     }
693   }
694
695   /**
696    * DOCUMENT ME!
697    */
698   public void tqli2() throws Exception
699   {
700     int n = rows;
701
702     int m;
703     int l;
704     int iter;
705     int i;
706     int k;
707     double s;
708     double r;
709     double p;
710     ;
711
712     double g;
713     double f;
714     double dd;
715     double c;
716     double b;
717
718     for (i = 2; i <= n; i++)
719     {
720       e[i - 2] = e[i - 1];
721     }
722
723     e[n - 1] = 0.0;
724
725     for (l = 1; l <= n; l++)
726     {
727       iter = 0;
728
729       do
730       {
731         for (m = l; m <= (n - 1); m++)
732         {
733           dd = Math.abs(d[m - 1]) + Math.abs(d[m]);
734
735           if ((Math.abs(e[m - 1]) + dd) == dd)
736           {
737             break;
738           }
739         }
740
741         if (m != l)
742         {
743           iter++;
744
745           if (iter == maxIter)
746           {
747             throw new Exception(MessageManager.formatMessage(
748                     "exception.matrix_too_many_iteration", new String[] {
749                         "tqli2", Integer.valueOf(maxIter).toString() }));
750           }
751           else
752           {
753             // System.out.println("Iteration " + iter);
754           }
755
756           g = (d[l] - d[l - 1]) / (2.0 * e[l - 1]);
757           r = Math.sqrt((g * g) + 1.0);
758           g = d[m - 1] - d[l - 1] + (e[l - 1] / (g + sign(r, g)));
759           c = 1.0;
760           s = c;
761           p = 0.0;
762
763           for (i = m - 1; i >= l; i--)
764           {
765             f = s * e[i - 1];
766             b = c * e[i - 1];
767
768             if (Math.abs(f) >= Math.abs(g))
769             {
770               c = g / f;
771               r = Math.sqrt((c * c) + 1.0);
772               e[i] = f * r;
773               s = 1.0 / r;
774               c *= s;
775             }
776             else
777             {
778               s = f / g;
779               r = Math.sqrt((s * s) + 1.0);
780               e[i] = g * r;
781               c = 1.0 / r;
782               s *= c;
783             }
784
785             g = d[i] - p;
786             r = ((d[i - 1] - g) * s) + (2.0 * c * b);
787             p = s * r;
788             d[i] = g + p;
789             g = (c * r) - b;
790
791             for (k = 1; k <= n; k++)
792             {
793               f = value[k - 1][i];
794               value[k - 1][i] = (s * value[k - 1][i - 1]) + (c * f);
795               value[k - 1][i - 1] = (c * value[k - 1][i - 1]) - (s * f);
796             }
797           }
798
799           d[l - 1] = d[l - 1] - p;
800           e[l - 1] = g;
801           e[m - 1] = 0.0;
802         }
803       } while (m != l);
804     }
805   }
806
807   /**
808    * Answers the first argument with the sign of the second argument
809    * 
810    * @param a
811    * @param b
812    * 
813    * @return
814    */
815   static double sign(double a, double b)
816   {
817     if (b < 0)
818     {
819       return -Math.abs(a);
820     }
821     else
822     {
823       return Math.abs(a);
824     }
825   }
826
827   /**
828    * Returns an array containing the values in the specified column
829    * 
830    * @param col
831    * 
832    * @return
833    */
834   public double[] getColumn(int col)
835   {
836     double[] out = new double[rows];
837
838     for (int i = 0; i < rows; i++)
839     {
840       out[i] = value[i][col];
841     }
842
843     return out;
844   }
845
846   /**
847    * DOCUMENT ME!
848    * 
849    * @param ps
850    *          DOCUMENT ME!
851    * @param format
852    */
853   @Override
854   public void printD(PrintStream ps, String format)
855   {
856     for (int j = 0; j < rows; j++)
857     {
858       Format.print(ps, format, d[j]);
859     }
860   }
861
862   /**
863    * DOCUMENT ME!
864    * 
865    * @param ps
866    *          DOCUMENT ME!
867    * @param format TODO
868    */
869   @Override
870   public void printE(PrintStream ps, String format)
871   {
872     for (int j = 0; j < rows; j++)
873     {
874       Format.print(ps, format, e[j]);
875     }
876   }
877
878   @Override
879   public double[] getD()
880   {
881     return d;
882   }
883
884   @Override
885   public double[] getE()
886   {
887     return e;
888   }
889   
890   @Override
891   public int height() {
892     return rows;
893   }
894
895   @Override
896   public int width()
897   {
898     return cols;
899   }
900
901   @Override
902   public double[] getRow(int i)
903   {
904     double[] row = new double[cols];
905     System.arraycopy(value[i], 0, row, 0, cols);
906     return row;
907   }
908
909   /**
910    * Returns a length 2 array of {minValue, maxValue} of all values in the
911    * matrix. Returns null if the matrix is null or empty.
912    * 
913    * @return
914    */
915   double[] findMinMax()
916   {
917     if (value == null)
918     {
919       return null;
920     }
921     double min = Double.MAX_VALUE;
922     double max = -Double.MAX_VALUE;
923     boolean empty = true;
924     for (double[] row : value)
925     {
926       if (row != null)
927       {
928         for (double x : row)
929         {
930           empty = false;
931           if (x > max)
932           {
933             max = x;
934           }
935           if (x < min)
936           {
937             min = x;
938           }
939         }
940       }
941     }
942     return empty ? null : new double[] { min, max };
943   }
944
945   /**
946    * {@inheritDoc}
947    */
948   @Override
949   public void reverseRange(boolean maxToZero)
950   {
951     if (value == null)
952     {
953       return;
954     }
955     double[] minMax = findMinMax();
956     if (minMax == null)
957     {
958       return; // empty matrix
959     }
960     double subtractFrom = maxToZero ? minMax[1] : minMax[0] + minMax[1];
961
962     for (double[] row : value)
963     {
964       if (row != null)
965       {
966         int j = 0;
967         for (double x : row)
968         {
969           row[j] = subtractFrom - x;
970           j++;
971         }
972       }
973     }
974   }
975
976   /**
977    * Multiplies every entry in the matrix by the given value.
978    * 
979    * @param
980    */
981   @Override
982   public void multiply(double by)
983   {
984     for (double[] row : value)
985     {
986       if (row != null)
987       {
988         for (int i = 0; i < row.length; i++)
989         {
990           row[i] *= by;
991         }
992       }
993     }
994   }
995 }