1 /*****************************************************************************
2 Major portions of this software are copyrighted by the Medical College
3 of Wisconsin, 1994-2000, and are released under the Gnu General Public
4 License, Version 2. See the file README.Copyright for details.
5 ******************************************************************************/
6
7 /*!
8 This file contains matrix and vector arithmetic routines.
9
10 File: matrix.c
11 Author: B. Douglas Ward
12 Date: 23 April 1997
13
14 Mod: Changed print format for functions matrix_print and vector_print.
15 Date: 05 August 1997
16
17 Mod: Changed initialization in function vector_create.
18 Date: 04 November 1997
19
20 Mod: Added routines matrix_file_write and matrix_file_read.
21 Date: 02 July 1999
22
23 Mod: Added routine for calculating square root of matrix.
24 Date: 30 September 1999
25
26 Mod: Added routines matrix_sprint and vector_sprint.
27 Date: 04 October 1999
28
29 Mod: Modified matrix_file_read to use mri_read_ascii routine.
30 Date: 12 January 2000
31
32 Mod: Changed return type of vector_dot from float to double.
33 Date: 13 April 2000
34
35 Mod: Added functions column_to_vector and matrix_extract_rows.
36 Date: 21 April 2000
37
38 Mod: Added test for missing matrix file name.
39 Date: 08 May 2000
40
41 Mod: Added "register" declarations and a few other things to speed
42 up calculations (including vector_create_noinit) -- RWCox.
43 Date: 28 Dec 2001
44
45 Mod: Allow matrices and vectors with zero rows and columns.
46 Date: 26 February 2002
47
48 Mod: Corrected errors in vector_multiply and vector_multiply_subtract
49 routines that would produce segmentation fault for certain input
50 matrices.
51 Date: 18 March 2003
52
53 Mod: Added UNROLL_VECMUL stuff from matrix.c to this file as well.
54 Added 'ipr' to matrix_print().
55 Added USE_ALTIVEC stuff for Macs.
56 Date: 03 Aug 2004
57
58 Mod: Added USE_SCSLBLAS stuff for SGI Altix.
59 Date: 01 Mar 2005
60
61 Mod: Freed memory for an orphaned matrix in matrix_sqrt function
62 Date: 26 Mar 2008 - drg
63
64 Mod: Added matrix_augment_01_columns, to match matrix.c.
65 Date: 19 Aug 2019 - rickr
66
67 */
68
69 #include "mri_image.h" /* moved here on 16 May 2005, for OS X Tiger */
70 extern MRI_IMAGE *mri_read_1D(char *) ;
71 extern void mri_free( MRI_IMAGE *im ) ;
72
73 #include <math.h>
74 #include <stdlib.h>
75 #include <stdio.h>
76 #include "matrix_f.h"
77 #include "cs.h"
78
79 /*---------------------------------------------------------------------*/
80 /** Vectorization macros:
81 - DOTP(n,x,y,z) computes the n-long dot product of vectors
82 x and y and puts the result into the place pointed to by z.
83 - VSUB(n,x,y,z) computes vector x-y into vector z.
84 - These are intended to be the fast method for doing these things. **/
85 /*---------------------------------------------------------------------*/
86
87 /* Solaris BLAS isn't used here because it is slower than
88 inline code for single precision, but faster for double. */
89
90 #undef SETUP_BLAS /* define this to use BLAS-1 functions */
91 #undef DOTP
92 #undef VSUB
93
94 #if defined(USE_ACCELERATE) /** Apple **/
95
96 # include <Accelerate/Accelerate.h>
97 # define DOTP(n,x,y,z) dotpr( x,1 , y,1 , z , n )
98 # define VSUB(n,x,y,z) vsub( x,1 , y,1 , z,1 , n )
99
100 #elif defined(USE_SCSLBLAS) /** SGI Altix **/
101
102 # include <scsl_blas.h>
103 # define SETUP_BLAS
104
105 #elif defined(USE_SUNPERF) /** Sun Solaris **/
106 # ifndef _SUNPERF_COMPLEX
107 # define _SUNPERF_COMPLEX
108 typedef struct { double r; double i; } doublecomplex;
109 # endif
110 # include <sunperf.h>
111 # define SETUP_BLAS
112
113 #elif defined(USE_ACML) /** AMD Core Math Library **/
114 # ifndef _ACML_COMPLEX
115 # define _ACML_COMPLEX
116 /* typedef struct { float real, imag; } complex; */
117 typedef struct { double real, imag; } doublecomplex;
118 # endif
119 # include <acml.h>
120 # define SETUP_BLAS
121
122 #endif /* vectorization special cases */
123
124 /* single precision BLAS-1 functions */
125
126 #ifdef SETUP_BLAS
127 # define DOTP(n,x,y,z) *(z)=sdot(n,x,1,y,1)
128 # define VSUB(n,x,y,z) (memcpy(z,x,sizeof(float)*n),saxpy(n,-1.0f,y,1,z,1))
129 #endif
130
131 #include <string.h>
132
133 /*---------------------------------------------------------------------------*/
134 /*!
135 Routine to print and error message and stop.
136 */
137
matrix_error(char * message)138 void matrix_error (char * message)
139 {
140 printf ("Matrix error: %s \n", message);
141 exit (1);
142 }
143
144
145 /*---------------------------------------------------------------------------*/
146 /*!
147 Initialize matrix data structure.
148 */
149
matrix_initialize(matrix * m)150 void matrix_initialize (matrix * m)
151 {
152 m->rows = 0;
153 m->cols = 0;
154 m->elts = NULL;
155 #ifndef DONT_USE_MATRIX_MAT
156 m->mat = NULL;
157 #endif
158 }
159
160
161 /*---------------------------------------------------------------------------*/
162 /*!
163 Destroy matrix data structure by deallocating memory.
164 */
165
matrix_destroy(matrix * m)166 void matrix_destroy (matrix * m)
167 {
168 if (m->elts != NULL){
169 #ifdef DONT_USE_MATRIX_MAT
170 int i ;
171 for( i=0 ; i < m->rows ; i++ )
172 if( m->elts[i] != NULL ) free(m->elts[i]) ;
173 #endif
174 free(m->elts) ;
175 }
176 #ifndef DONT_USE_MATRIX_MAT
177 if( m->mat != NULL) free (m->mat) ;
178 #endif
179 matrix_initialize (m);
180 }
181
182 /*---------------------------------------------------------------------------*/
183 /*!
184 Create matrix data structure by allocating memory and initializing values.
185 */
186
matrix_create(int rows,int cols,matrix * m)187 void matrix_create (int rows, int cols, matrix * m)
188 {
189 register int i, j;
190
191 matrix_destroy (m);
192
193 if ((rows < 0) || (cols < 0))
194 matrix_error ("Illegal dimensions for new matrix");
195
196 m->rows = rows;
197 m->cols = cols;
198 if ((rows < 1) || (cols < 1)) return;
199
200 m->elts = (float **) malloc (sizeof(float *) * rows);
201 if (m->elts == NULL)
202 matrix_error ("Memory allocation error");
203
204 #ifdef DONT_USE_MATRIX_MAT
205 for (i = 0; i < rows; i++){
206 m->elts[i] = (float *) calloc (sizeof(float) , cols);
207 if (m->elts[i] == NULL) matrix_error ("Memory allocation error");
208 }
209 #else
210 m->mat = (float *) calloc( sizeof(float) , rows*cols ) ;
211 if( m->mat == NULL )
212 matrix_error ("Memory allocation error");
213 for (i = 0; i < rows; i++)
214 m->elts[i] = m->mat + (i*cols) ; /* 04 Mar 2005: offsets into mat */
215 #endif
216 }
217
218
219 /*---------------------------------------------------------------------------*/
220 /*!
221 Print contents of matrix m.
222 */
223
matrix_print(matrix m)224 void matrix_print (matrix m)
225 {
226 int i, j;
227 int rows, cols;
228 float val ;
229 int ipr ;
230
231 rows = m.rows; if( rows < 1 ) return ;
232 cols = m.cols; if( cols < 1 ) return ;
233
234 for( i=0 ; i < rows ; i++ ){
235 for( j=0 ; j < cols ; j++ ){
236 val = (int)m.elts[i][j] ;
237 if( val != m.elts[i][j] || fabs(val) > 9.0f ) goto zork ;
238 }
239 }
240 zork:
241 ipr = (i==rows && j==cols) ;
242
243 for (i = 0; i < rows; i++)
244 {
245 for (j = 0; j < cols; j++)
246 if( ipr ) printf (" %2d" , (int)m.elts[i][j]);
247 else printf (" %10.4g", m.elts[i][j]);
248 printf (" \n");
249 }
250 printf (" \n"); fflush(stdout);
251 }
252
253
254 /*---------------------------------------------------------------------------*/
255 /*!
256 Print label and contents of matrix m.
257 */
258
matrix_sprint(char * s,matrix m)259 void matrix_sprint (char * s, matrix m)
260 {
261 printf ("%s \n", s);
262
263 matrix_print (m);
264 }
265
266
267 /*---------------------------------------------------------------------------*/
268 /*!
269 Print contents of matrix m to specified file.
270 */
271
matrix_file_write(char * filename,matrix m)272 void matrix_file_write (char * filename, matrix m)
273 {
274 int i, j;
275 int rows, cols;
276 FILE * outfile = NULL;
277
278
279 /*----- First, check for empty file name -----*/
280 if (filename == NULL) matrix_error ("Missing matrix file name");
281
282
283 outfile = fopen (filename, "w");
284
285 rows = m.rows;
286 cols = m.cols;
287
288 for (i = 0; i < rows; i++)
289 {
290 for (j = 0; j < cols; j++)
291 fprintf (outfile, " %g", m.elts[i][j]);
292 fprintf (outfile, " \n");
293 }
294 fprintf (outfile, " \n");
295
296 fclose (outfile);
297 }
298
299 /*---------------------------------------------------------------------------*/
300 /*!
301 Manual entry of matrix data.
302 */
303
matrix_enter(matrix * m)304 void matrix_enter (matrix * m)
305 {
306 int rows, cols;
307 int i, j;
308 float fval;
309
310 printf ("Enter number of rows: "); fflush(stdout);
311 scanf ("%d", &rows);
312 printf ("Enter number of cols: "); fflush(stdout);
313 scanf ("%d", &cols);
314
315 matrix_create (rows, cols, m);
316
317 for (i = 0; i < rows; i++)
318 for (j = 0; j < cols; j++)
319 {
320 printf ("elts[%d][%d] = ", i, j); fflush(stdout);
321 scanf ("%f", &fval);
322 m->elts[i][j] = fval;
323 }
324 }
325
326
327 /*---------------------------------------------------------------------------*/
328 /*!
329 Read contents of matrix m from specified file.
330 If unable to read matrix from file, or matrix has wrong dimensions:
331 If error_exit flag is set, then print error message and exit.
332 Otherwise, return null matrix.
333 */
334
matrix_file_read(char * filename,int rows,int cols,matrix * m,int error_exit)335 void matrix_file_read (char *filename, int rows, int cols, matrix *m,
336 int error_exit)
337 {
338 int i, j;
339
340 MRI_IMAGE *im, *flim; /* pointers to image structures
341 -- used to read ASCII file */
342 float * far; /* pointer to MRI_IMAGE floating point data */
343 char message [80]; /* error message */
344
345
346 /*----- First, check for empty file name -----*/
347 if (filename == NULL) matrix_error ("Missing matrix file name");
348
349
350 /*----- Read the matrix file -----*/
351 flim = mri_read_1D (filename);
352 if (flim == NULL)
353 if (error_exit)
354 {
355 sprintf (message, "Unable to read matrix from file: %s", filename);
356 matrix_error (message);
357 }
358 else
359 {
360 matrix_destroy (m);
361 return;
362 }
363
364
365 /*----- Set pointer to data -----*/
366 far = MRI_FLOAT_PTR(flim);
367
368
369 /*----- Test for correct dimensions -----*/
370 if ( (rows != flim->nx) || (cols != flim->ny) )
371 if (error_exit)
372 {
373 sprintf (message,
374 "In matrix file: %s Expected: %d x %d Actual: %d x %d",
375 filename, rows, cols, flim->nx, flim->ny);
376 matrix_error (message);
377 }
378 else
379 {
380 matrix_destroy (m);
381 return;
382 }
383
384 matrix_create (rows, cols, m);
385
386 /*----- Copy data from image structure to matrix structure -----*/
387 for (i = 0; i < rows; i++)
388 for (j = 0; j < cols; j++)
389 m->elts[i][j] = far[i + j*rows];
390
391 mri_free (flim); flim = NULL;
392
393 }
394
395
396 /*---------------------------------------------------------------------------*/
397 /*!
398 Convert simple array to matrix structure.
399 */
400
array_to_matrix(int rows,int cols,float ** f,matrix * m)401 void array_to_matrix (int rows, int cols, float ** f, matrix * m)
402 {
403 register int i, j;
404
405 matrix_create (rows, cols, m);
406
407 for (i = 0; i < rows; i++)
408 for (j = 0; j < cols; j++)
409 m->elts[i][j] = f[i][j];
410 }
411
412
413 /*---------------------------------------------------------------------------*/
414 /*!
415 Make a copy of the first matrix, return copy as the second matrix.
416 */
417
matrix_equate(matrix a,matrix * b)418 void matrix_equate (matrix a, matrix * b)
419 {
420 register int i, j;
421 register int rows, cols;
422
423 rows = a.rows;
424 cols = a.cols;
425
426 matrix_create (rows, cols, b);
427
428 for (i = 0; i < rows; i++){
429 #if 0
430 for (j = 0; j < cols; j++)
431 b->elts[i][j] = a.elts[i][j];
432 #else
433 if( cols > 0 )
434 memcpy( b->elts[i] , a.elts[i] , sizeof(float )*cols ) ; /* RWCox */
435 #endif
436 }
437 }
438
439
440 /*---------------------------------------------------------------------------*/
441 /*!
442 Extract p columns (specified by list) from matrix a. Result is matrix b.
443 */
444
matrix_extract(matrix a,int p,int * list,matrix * b)445 void matrix_extract (matrix a, int p, int * list, matrix * b)
446 {
447 register int i, j;
448 register int rows, cols;
449
450 rows = a.rows;
451 cols = p;
452
453 matrix_create (rows, cols, b);
454
455 for (i = 0; i < rows; i++)
456 for (j = 0; j < cols; j++)
457 b->elts[i][j] = a.elts[i][list[j]];
458 }
459
460
461 /*---------------------------------------------------------------------------*/
462 /*!
463 Extract p rows (specified by list) from matrix a. Result is matrix b.
464 */
465
matrix_extract_rows(matrix a,int p,int * list,matrix * b)466 void matrix_extract_rows (matrix a, int p, int * list, matrix * b)
467 {
468 register int i, j;
469 register int rows, cols;
470
471 rows = p;
472 cols = a.cols;
473
474 matrix_create (rows, cols, b);
475
476 for (i = 0; i < rows; i++)
477 for (j = 0; j < cols; j++)
478 b->elts[i][j] = a.elts[list[i]][j];
479 }
480
481 /*---------------------------------------------------------------------------*/
482 /*!
483 Add columns that are all 0 except for a single 1, as indicated. [16 Aug 2019]
484 For use in 3dDeconvolve experimentation [RWC]
485 Dupe from matrix.c. [19 Aug 2019 rickr].
486 */
487
matrix_augment_01_columns(matrix a,int nadd,int * addlist,matrix * b)488 void matrix_augment_01_columns( matrix a, int nadd, int *addlist, matrix *b )
489 {
490 int arows,brows , acols,bcols , i,j,k,aa ;
491
492 if( b == NULL ) return ; /* bad input */
493
494 if( nadd <= 0 || addlist == NULL ){ /* nothing to do but copy input */
495 matrix_equate(a,b) ; return ;
496 }
497
498 /* check addlist for bad entries */
499
500 for( aa=0 ; aa < nadd ; aa++ ){
501 if( addlist[aa] < 0 || addlist[aa] >= a.rows ){
502 fprintf(stderr,"** ERROR: bad index in matrix_augment_01_columns\n") ;
503 return ;
504 }
505 }
506
507 arows = brows = a.rows ;
508 acols = a.cols ;
509 bcols = acols + nadd ;
510
511 matrix_create( brows , bcols , b ) ;
512
513 /* copy original part */
514
515 for( i=0 ; i < brows ; i++ )
516 for( j=0 ; j < acols ; j++ ) b->elts[i][j] = a.elts[i][j] ;
517
518 /* add new cols */
519
520 for( aa=0 ; aa < nadd ; aa++ ){
521 k = addlist[aa] ; j = acols+aa ;
522 for( i=0 ; i < brows ; i++ )
523 b->elts[i][j] = (i==k) ? 1.0 : 0.0 ;
524 }
525
526 return ;
527 }
528
529
530 /*---------------------------------------------------------------------------*/
531 /*!
532 Create n x n identity matrix.
533 */
534
matrix_identity(int n,matrix * m)535 void matrix_identity (int n, matrix * m)
536 {
537 register int i, j;
538
539 if (n < 0)
540 matrix_error ("Illegal dimensions for identity matrix");
541
542 matrix_create (n, n, m);
543
544 for (i = 0; i < n; i++)
545 for (j = 0; j < n; j++)
546 if (i == j) m->elts[i][j] = 1.0;
547 else m->elts[i][j] = 0.0;
548 }
549
550
551 /*---------------------------------------------------------------------------*/
552 /*!
553 Add matrix a to matrix b. Result is matrix c.
554 */
555
matrix_add(matrix a,matrix b,matrix * c)556 void matrix_add (matrix a, matrix b, matrix * c)
557 {
558 register int rows, cols;
559 register int i, j;
560
561 if ((a.rows != b.rows) || (a.cols != b.cols))
562 matrix_error ("Incompatible dimensions for matrix addition");
563
564 rows = a.rows;
565 cols = a.cols;
566
567 matrix_create (rows, cols, c);
568
569 for (i = 0; i < rows; i++)
570 for (j = 0; j < cols; j++)
571 c->elts[i][j] = a.elts[i][j] + b.elts[i][j];
572 }
573
574
575 /*---------------------------------------------------------------------------*/
576 /*!
577 Subtract matrix b from matrix a. Result is matrix c.
578 */
579
matrix_subtract(matrix a,matrix b,matrix * c)580 void matrix_subtract (matrix a, matrix b, matrix * c)
581 {
582 register int rows, cols;
583 register int i, j;
584
585 if ((a.rows != b.rows) || (a.cols != b.cols))
586 matrix_error ("Incompatible dimensions for matrix subtraction");
587
588 rows = a.rows;
589 cols = a.cols;
590
591 matrix_create (rows, cols, c);
592
593 for (i = 0; i < rows; i++)
594 for (j = 0; j < cols; j++)
595 c->elts[i][j] = a.elts[i][j] - b.elts[i][j];
596 }
597
598
599 /*---------------------------------------------------------------------------*/
600 /*!
601 Multiply matrix a by matrix b. Result is matrix c.
602 */
603
matrix_multiply(matrix a,matrix b,matrix * c)604 void matrix_multiply (matrix a, matrix b, matrix * c)
605 {
606 int rows, cols;
607 register int i, j, k;
608 register float sum ;
609
610 if (a.cols != b.rows)
611 matrix_error ("Incompatible dimensions for matrix multiplication");
612
613 rows = a.rows;
614 cols = b.cols;
615
616 matrix_create (rows, cols, c);
617
618 for (i = 0; i < rows; i++)
619 for (j = 0; j < cols; j++)
620 {
621 sum = 0.0 ;
622 for (k = 0; k < a.cols; k++)
623 sum += a.elts[i][k] * b.elts[k][j];
624 c->elts[i][j] = sum;
625 }
626 }
627
628
629 /*---------------------------------------------------------------------------*/
630 /*!
631 Multiply matrix a by scalar constant k. Result is matrix c.
632 */
633
matrix_scale(float k,matrix a,matrix * c)634 void matrix_scale (float k, matrix a, matrix * c)
635 {
636 register int rows, cols;
637 register int i, j;
638
639 rows = a.rows;
640 cols = a.cols;
641
642 matrix_create (rows, cols, c);
643
644 for (i = 0; i < rows; i++)
645 for (j = 0; j < cols; j++)
646 c->elts[i][j] = k * a.elts[i][j];
647 }
648
649
650 /*---------------------------------------------------------------------------*/
651 /*!
652 Take transpose of matrix a. Result is matrix t.
653 */
654
matrix_transpose(matrix a,matrix * t)655 void matrix_transpose (matrix a, matrix * t)
656 {
657 register int rows, cols;
658 register int i, j;
659
660 rows = a.cols;
661 cols = a.rows;
662
663 matrix_create (rows, cols, t);
664 for (i = 0; i < rows; i++)
665 for (j = 0; j < cols; j++)
666 t->elts[i][j] = a.elts[j][i];
667 }
668
669
670 /*---------------------------------------------------------------------------*/
671 /*!
672 Use Gaussian elimination to calculate inverse of matrix a. Result is
673 matrix ainv.
674 */
675
matrix_inverse(matrix a,matrix * ainv)676 int matrix_inverse (matrix a, matrix * ainv)
677 {
678 const float epsilon = 1.0e-10;
679 matrix tmp;
680 register int i, j, ii, n;
681 register float fval;
682 register float fmax;
683 register float * p;
684
685 matrix_initialize (&tmp);
686
687
688 if (a.rows != a.cols)
689 matrix_error ("Illegal dimensions for matrix inversion");
690
691
692 n = a.rows;
693 matrix_identity (n, ainv);
694 matrix_equate (a, &tmp);
695
696 for (i = 0; i < n; i++)
697 {
698 fmax = fabs(tmp.elts[i][i]);
699 for (j = i+1; j < n; j++)
700 if (fabs(tmp.elts[j][i]) > fmax)
701 {
702 fmax = fabs(tmp.elts[j][i]);
703 p = tmp.elts[i];
704 tmp.elts[i] = tmp.elts[j];
705 tmp.elts[j] = p;
706 p = ainv->elts[i];
707 ainv->elts[i] = ainv->elts[j];
708 ainv->elts[j] = p;
709 }
710
711 if (fmax < epsilon)
712 {
713 matrix_destroy (&tmp);
714 return (0);
715 }
716
717 fval = 1.0 / tmp.elts[i][i]; /* RWCox: change division by this to */
718 for (j = 0; j < n; j++) /* multiplication by 1.0/this */
719 {
720 tmp.elts[i][j] *= fval;
721 ainv->elts[i][j] *= fval;
722 }
723 for (ii = 0; ii < n; ii++)
724 if (ii != i)
725 {
726 fval = tmp.elts[ii][i];
727 for (j = 0; j < n; j++)
728 {
729 tmp.elts[ii][j] -= fval*tmp.elts[i][j];
730 ainv->elts[ii][j] -= fval*ainv->elts[i][j];
731 }
732 }
733
734 }
735 matrix_destroy (&tmp);
736 return (1);
737 }
738
739 /*---------------------------------------------------------------------------*/
740 /*!
741 Use Gaussian elimination to calculate inverse of matrix a, with diagonal
742 scaling applied for stability. Result is matrix ainv.
743 */
744
matrix_inverse_dsc(matrix a,matrix * ainv)745 int matrix_inverse_dsc (matrix a, matrix * ainv) /* 15 Jul 2004 - RWCox */
746 {
747 matrix atmp;
748 register int i, j, n;
749 register double *diag ;
750 int mir ;
751
752 if (a.rows != a.cols)
753 matrix_error ("Illegal dimensions for matrix inversion");
754
755 matrix_initialize (&atmp);
756
757 n = a.rows;
758 matrix_equate (a, &atmp);
759 diag = (double *)malloc( sizeof(double)*n ) ;
760 for( i=0 ; i < n ; i++ ){
761 diag[i] = fabs(atmp.elts[i][i]) ;
762 if( diag[i] == 0.0 ) diag[i] = 1.0 ; /* shouldn't happen? */
763 diag[i] = 1.0 / sqrt(diag[i]) ;
764 }
765
766 for( i=0 ; i < n ; i++ ) /* scale a */
767 for( j=0 ; j < n ; j++ )
768 atmp.elts[i][j] *= diag[i]*diag[j] ;
769
770 mir = matrix_inverse( atmp , ainv ) ; /* invert */
771
772 for( i=0 ; i < n ; i++ ) /* scale inverse */
773 for( j=0 ; j < n ; j++ )
774 ainv->elts[i][j] *= diag[i]*diag[j] ;
775
776 matrix_destroy (&atmp); free((void *)diag) ;
777 return (mir);
778 }
779
780 /*---------------------------------------------------------------------------*/
781 /*!
782 Calculate square root of symmetric positive definite matrix a.
783 Result is matrix s.
784 */
785
matrix_sqrt(matrix a,matrix * s)786 int matrix_sqrt (matrix a, matrix * s)
787 {
788 const int MAX_ITER = 100;
789 int n;
790 int ok;
791 int iter;
792 register float sse, psse;
793 register int i, j;
794 matrix x, xinv, axinv, xtemp, error;
795
796 matrix_initialize (&x);
797 matrix_initialize (&xinv);
798 matrix_initialize (&axinv);
799 matrix_initialize (&xtemp);
800 matrix_initialize (&error);
801
802
803 if (a.rows != a.cols)
804 matrix_error ("Illegal dimensions for matrix square root");
805
806
807 n = a.rows;
808 matrix_identity (n, &x);
809
810
811 psse = 1.0e+30;
812 for (iter = 0; iter < MAX_ITER; iter++)
813 {
814 ok = matrix_inverse (x, &xinv);
815 if (! ok) return (0);
816 matrix_multiply (a, xinv, &axinv);
817 matrix_add (x, axinv, &xtemp);
818 matrix_scale (0.5, xtemp, &x);
819
820 matrix_multiply (x, x, &xtemp);
821 matrix_subtract (a, xtemp, &error);
822 sse = 0.0;
823 for (i = 0; i < n; i++)
824 for (j = 0; j < n; j++)
825 sse += error.elts[i][j] * error.elts[i][j] ;
826
827 if (sse >= psse) break;
828
829 psse = sse;
830 }
831
832 if (iter == MAX_ITER) return (0);
833
834 matrix_equate (x, s);
835
836 matrix_destroy (&x);
837 matrix_destroy (&xinv);
838 matrix_destroy (&axinv);
839 matrix_destroy (&xtemp);
840 matrix_destroy (&error); /* destroy error matrix too - 26 Mar 2008 drg */
841
842 return (1);
843
844 }
845
846
847 /*---------------------------------------------------------------------------*/
848 /*!
849 Initialize vector data structure.
850 */
851
vector_initialize(vector * v)852 void vector_initialize (vector * v)
853 {
854 v->dim = 0;
855 v->elts = NULL;
856 }
857
858
859 /*---------------------------------------------------------------------------*/
860 /*!
861 Destroy vector data structure by deallocating memory.
862 */
863
vector_destroy(vector * v)864 void vector_destroy (vector * v)
865 {
866 if (v->elts != NULL) free (v->elts);
867 vector_initialize (v);
868 }
869
870
871 /*---------------------------------------------------------------------------*/
872 /*!
873 Create vector v by allocating memory and initializing values.
874 */
875
vector_create(int dim,vector * v)876 void vector_create (int dim, vector * v)
877 {
878 register int i;
879
880 vector_destroy (v);
881
882 if (dim < 0) matrix_error ("Illegal dimensions for new vector");
883
884 v->dim = dim;
885 if (dim < 1) return;
886
887 v->elts = (float *) calloc (sizeof(float) , dim);
888 if (v->elts == NULL)
889 matrix_error ("Memory allocation error");
890 }
891
892 /*---------------------------------------------------------------------------*/
vector_create_noinit(int dim,vector * v)893 static void vector_create_noinit(int dim, vector * v) /* 28 Dec 2001: RWCox */
894 {
895 register int i;
896
897 vector_destroy (v);
898
899 if (dim < 0) matrix_error ("Illegal dimensions for new vector");
900
901 v->dim = dim;
902 if (dim < 1) return;
903
904 v->elts = (float *) malloc (sizeof(float ) * dim);
905 if (v->elts == NULL)
906 matrix_error ("Memory allocation error");
907 }
908
909 /*---------------------------------------------------------------------------*/
910 /*!
911 Print contents of vector v.
912 */
913
vector_print(vector v)914 void vector_print (vector v)
915 {
916 int i;
917
918 for (i = 0; i < v.dim; i++)
919 printf (" %10.4g \n", v.elts[i]);
920 printf (" \n"); fflush(stdout);
921
922 }
923
924
925 /*---------------------------------------------------------------------------*/
926 /*!
927 Print label and contents of vector v.
928 */
929
vector_sprint(char * s,vector v)930 void vector_sprint (char * s, vector v)
931 {
932 printf ("%s \n", s);
933
934 vector_print (v);
935 }
936
937
938 /*---------------------------------------------------------------------------*/
939 /*!
940 Copy vector a. Result is vector b.
941 */
942
vector_equate(vector a,vector * b)943 void vector_equate (vector a, vector * b)
944 {
945 register int i, dim;
946
947 dim = a.dim;
948
949 vector_create_noinit (dim, b);
950
951 #if 0
952 for (i = 0; i < dim; i++)
953 b->elts[i] = a.elts[i];
954 #else
955 if( dim > 0 )
956 memcpy( b->elts , a.elts , sizeof(float )*dim ) ; /* RWCox */
957 #endif
958 }
959
960
961 /*---------------------------------------------------------------------------*/
962 /*!
963 Convert simple array f into vector v.
964 */
965
array_to_vector(int dim,float * f,vector * v)966 void array_to_vector (int dim, float * f, vector * v)
967 {
968 register int i;
969
970 vector_create_noinit (dim, v);
971
972 for (i = 0; i < dim; i++)
973 v->elts[i] = f[i];
974 }
975
976
977
978 /*---------------------------------------------------------------------------*/
979 /*!
980 Convert column c of matrix m into vector v.
981 */
982
column_to_vector(matrix m,int c,vector * v)983 void column_to_vector (matrix m, int c, vector * v)
984 {
985 register int i;
986 register int dim;
987
988 dim = m.rows;
989 vector_create_noinit (dim, v);
990
991 for (i = 0; i < dim; i++)
992 v->elts[i] = m.elts[i][c];
993 }
994
995
996
997 /*---------------------------------------------------------------------------*/
998 /*!
999 Convert vector v into array f.
1000 */
1001
vector_to_array(vector v,float * f)1002 void vector_to_array (vector v, float * f)
1003 {
1004 register int i;
1005
1006 for (i = 0; i < v.dim; i++)
1007 f[i] = v.elts[i];
1008 }
1009
1010
1011 /*---------------------------------------------------------------------------*/
1012 /*!
1013 Add vector a to vector b. Result is vector c.
1014 */
1015
vector_add(vector a,vector b,vector * c)1016 void vector_add (vector a, vector b, vector * c)
1017 {
1018 register int i, dim;
1019
1020 if (a.dim != b.dim)
1021 matrix_error ("Incompatible dimensions for vector addition");
1022
1023 dim = a.dim;
1024
1025 vector_create_noinit (dim, c);
1026
1027 for (i = 0; i < dim; i++)
1028 c->elts[i] = a.elts[i] + b.elts[i];
1029 }
1030
1031
1032 /*---------------------------------------------------------------------------*/
1033 /*!
1034 Subtract vector b from vector a. Result is vector c.
1035 */
1036
vector_subtract(vector a,vector b,vector * c)1037 void vector_subtract (vector a, vector b, vector * c)
1038 {
1039 register int i, dim;
1040 register float *aa,*bb,*cc ;
1041
1042 if (a.dim != b.dim)
1043 matrix_error ("Incompatible dimensions for vector subtraction");
1044
1045 dim = a.dim;
1046
1047 vector_create_noinit (dim, c);
1048
1049 aa = a.elts ; bb = b.elts ; cc = c->elts ;
1050 for (i = 0; i < dim; i++)
1051 #if 0
1052 c->elts[i] = a.elts[i] - b.elts[i];
1053 #else
1054 cc[i] = aa[i] - bb[i] ;
1055 #endif
1056 }
1057
1058 #define UNROLL_VECMUL /* RWCox */
1059 #undef P
1060 #define P(z) aa[z]*bb[z] /* elementary product [16 Oct 2006] */
1061
1062 /*---------------------------------------------------------------------------*/
1063 /*!
1064 Right multiply matrix a by vector b. Result is vector c.
1065 */
vector_multiply(matrix a,vector b,vector * c)1066 void vector_multiply (matrix a, vector b, vector *c)
1067 {
1068 register int rows, cols;
1069 register int i, j;
1070 register float sum ;
1071 register float *bb , *cc ;
1072 #ifdef DOTP
1073 float **aa ;
1074 #else
1075 register float *aa ;
1076 #endif
1077
1078 if (a.cols != b.dim)
1079 matrix_error ("Incompatible dimensions for vector multiplication");
1080
1081 rows = a.rows;
1082 cols = a.cols;
1083
1084 vector_create_noinit (rows, c);
1085
1086 if( cols <= 0 ){
1087 for( i=0 ; i < rows ; i++ ) c->elts[i] = 0.0f ;
1088 return ;
1089 }
1090
1091 bb = b.elts ; cc = c->elts ;
1092
1093 #ifdef DOTP
1094 aa = a.elts ; cc = c->elts ;
1095 i = rows%2 ;
1096 if( i == 1 ) DOTP(cols,aa[0],bb,cc) ;
1097 for( ; i < rows ; i+=2 ){
1098 DOTP(cols,aa[i] ,bb,cc+i ) ;
1099 DOTP(cols,aa[i+1],bb,cc+(i+1)) ;
1100 }
1101 #else
1102
1103 #ifdef UNROLL_VECMUL
1104 switch( cols%4 ){ /* unroll inner loop by 4 */
1105 case 0:
1106 for (i = 0; i < rows; i++){
1107 sum = 0.0 ; aa = a.elts[i] ;
1108 for (j = 0; j < cols; j+=4 ) sum += P(j) + P(j+1) + P(j+2) + P(j+3);
1109 cc[i] = sum ;
1110 }
1111 break ;
1112 case 1:
1113 for (i = 0; i < rows; i++){
1114 aa = a.elts[i] ; sum = P(0) ;
1115 for (j = 1; j < cols; j+=4 ) sum += P(j) + P(j+1) + P(j+2) + P(j+3);
1116 cc[i] = sum ;
1117 }
1118 break ;
1119 case 2:
1120 for (i = 0; i < rows; i++){
1121 aa = a.elts[i] ; sum = P(0)+P(1) ;
1122 for (j = 2; j < cols; j+=4 ) sum += P(j) + P(j+1) + P(j+2) + P(j+3);
1123 cc[i] = sum ;
1124 }
1125 break ;
1126 case 3:
1127 for (i = 0; i < rows; i++){
1128 aa = a.elts[i] ; sum = P(0)+P(1)+P(2) ;
1129 for (j = 3; j < cols; j+=4 ) sum += P(j) + P(j+1) + P(j+2) + P(j+3);
1130 cc[i] = sum ;
1131 }
1132 break ;
1133 }
1134 #else
1135 for (i = 0; i < rows; i++){ /** the simplest C code **/
1136 sum = 0.0f ; aa = a.elts[i] ;
1137 for (j = 0; j < cols; j++ ) sum += aa[j]*bb[j] ;
1138 cc[i] = sum ;
1139 }
1140 #endif /* UNROLL_VECMUL */
1141
1142 #endif /* DOTP */
1143
1144 }
1145
1146 /*---------------------------------------------------------------------------*/
1147 /*!
1148 Right multiply matrix a-transpose by vector b. Result is vector c.
1149 */
vector_multiply_transpose(matrix a,vector b,vector * c)1150 void vector_multiply_transpose (matrix a, vector b, vector * c)
1151 {
1152 register int rows, cols;
1153 register int i, j;
1154 register float *bb ;
1155 register float bj ;
1156 register float *aa , *cc ;
1157
1158 if (a.rows != b.dim){
1159 char str[444] ;
1160 sprintf(str,
1161 "Incompatible dimensions for vector_multiply_transpose: %dx%d X %d",
1162 a.rows,a.cols,b.dim ) ;
1163 matrix_error(str) ;
1164 }
1165
1166 rows = a.rows; cols = a.cols;
1167
1168 vector_create(cols, c); /* initialized to 0 */
1169
1170 if( rows <= 0 ) return ;
1171
1172 bb = b.elts ; cc = c->elts ;
1173
1174 #ifdef UNROLL_VECMUL
1175 switch( cols%2 ){
1176 case 0:
1177 for( j=0 ; j < rows ; j++ ){
1178 aa = a.elts[j] ; bj = bb[j] ;
1179 for( i=0 ; i < cols ; i+=2 ){
1180 cc[i] += aa[i] *bj ;
1181 cc[i+1] += aa[i+1]*bj ;
1182 }
1183 }
1184 break ;
1185
1186 case 1:
1187 for( j=0 ; j < rows ; j++ ){
1188 aa = a.elts[j] ; bj = bb[j] ;
1189 cc[0] += aa[0]*bj ;
1190 for( i=1 ; i < cols ; i+=2 ){
1191 cc[i] += aa[i] *bj ;
1192 cc[i+1] += aa[i+1]*bj ;
1193 }
1194 }
1195 break ;
1196 }
1197 #else
1198 for( j=0 ; j < rows ; j++ ){
1199 aa = a.elts[j] ; bj = bb[j] ;
1200 for( i=0 ; i < cols ; i++ ) cc[i] += aa[i]*bj ;
1201 }
1202 #endif
1203
1204 return ;
1205 }
1206
1207
1208 /*---------------------------------------------------------------------------*/
1209 /*!
1210 Compute d = c-a*b: a is a matrix; b,c,d are vectors -- RWCox
1211 26 Feb 2002: return value is sum of squares of d vector
1212 */
1213
vector_multiply_subtract(matrix a,vector b,vector c,vector * d)1214 float vector_multiply_subtract (matrix a, vector b, vector c, vector * d)
1215 {
1216 register int rows, cols;
1217 register int i, j;
1218 register float *bb , *dd,*cc ;
1219 #ifdef DOTP
1220 float qsum,sum , **aa , *ee ;
1221 #else
1222 register float qsum,sum, *aa ;
1223 #endif
1224
1225 if (a.cols != b.dim || a.rows != c.dim )
1226 matrix_error ("Incompatible dimensions for vector multiplication-subtraction");
1227
1228 rows = a.rows;
1229 cols = a.cols;
1230
1231 vector_create_noinit (rows, d);
1232
1233 if( cols <= 0 ){
1234 qsum = 0.0f ;
1235 for( i=0 ; i < rows ; i++ ){
1236 d->elts[i] = c.elts[i] ;
1237 qsum += d->elts[i] * d->elts[i] ;
1238 }
1239 return qsum ;
1240 }
1241
1242 qsum = 0.0f ; bb = b.elts ; dd = d->elts ; cc = c.elts ;
1243
1244 #ifdef DOTP
1245 aa = a.elts ;
1246 ee = (float *)malloc(sizeof(float)*rows) ;
1247 i = rows%2 ;
1248 if( i == 1 ) DOTP(cols,aa[0],bb,ee) ;
1249 for( ; i < rows ; i+=2 ){
1250 DOTP(cols,aa[i] ,bb,ee+i ) ;
1251 DOTP(cols,aa[i+1],bb,ee+(i+1)) ;
1252 }
1253 VSUB(rows,cc,ee,dd) ;
1254 DOTP(rows,dd,dd,&qsum) ;
1255 free((void *)ee) ;
1256 #else
1257
1258 #ifdef UNROLL_VECMUL
1259 switch( cols%4 ){ /* unroll inner loop by 4 */
1260 case 0:
1261 for (i = 0; i < rows; i++){
1262 aa = a.elts[i] ; sum = cc[i] ;
1263 for (j = 0; j < cols; j+=4 ) sum -= P(j) + P(j+1) + P(j+2) + P(j+3);
1264 dd[i] = sum ; qsum += sum*sum ;
1265 }
1266 break ;
1267 case 1:
1268 for (i = 0; i < rows; i++){
1269 aa = a.elts[i] ; sum = cc[i]-P(0) ;
1270 for (j = 1; j < cols; j+=4 ) sum -= P(j) + P(j+1) + P(j+2) + P(j+3);
1271 dd[i] = sum ; qsum += sum*sum ;
1272 }
1273 break ;
1274 case 2:
1275 for (i = 0; i < rows; i++){
1276 aa = a.elts[i] ; sum = cc[i]-P(0)-P(1) ;
1277 for (j = 2; j < cols; j+=4 ) sum -= P(j) + P(j+1) + P(j+2) + P(j+3);
1278 dd[i] = sum ; qsum += sum*sum ;
1279 }
1280 break ;
1281 case 3:
1282 for (i = 0; i < rows; i++){
1283 aa = a.elts[i] ; sum = cc[i]-P(0)-P(1)-P(2) ;
1284 for (j = 3; j < cols; j+=4 ) sum -= P(j) + P(j+1) + P(j+2) + P(j+3);
1285 dd[i] = sum ; qsum += sum*sum ;
1286 }
1287 break ;
1288 }
1289 #else
1290 for (i = 0; i < rows; i++){ /** the simplest C code **/
1291 aa = a.elts[i] ; sum = cc[i] ;
1292 for (j = 0; j < cols; j++) sum -= aa[j] * bb[j] ;
1293 dd[i] = sum ; qsum += sum*sum ;
1294 }
1295 #endif /* UNROLL_VECMUL */
1296
1297 #endif /* DOTP */
1298
1299 return qsum ; /* 26 Feb 2003 */
1300 }
1301
1302 /*---------------------------------------------------------------------------*/
1303 /*!
1304 Calculate dot product of vector a with vector b.
1305 */
1306
vector_dot(vector a,vector b)1307 float vector_dot (vector a, vector b)
1308 {
1309 register int i, dim;
1310 register float sum;
1311 register float *aa , *bb ;
1312
1313 if (a.dim != b.dim)
1314 matrix_error ("Incompatible dimensions for vector dot product");
1315
1316 dim = a.dim;
1317
1318 sum = 0.0f;
1319 aa = a.elts ; bb = b.elts ;
1320 for (i = 0; i < dim; i++)
1321 #if 0
1322 sum += a.elts[i] * b.elts[i];
1323 #else
1324 sum += aa[i] * bb[i] ;
1325 #endif
1326
1327 return (sum);
1328 }
1329
1330 /*--------------------------------------------------------------------------*/
1331 /*!
1332 Calculate dot product of vector a with itself -- 28 Dec 2001, RWCox.
1333 */
1334
vector_dotself(vector a)1335 float vector_dotself( vector a )
1336 {
1337 register int i, dim;
1338 register float sum;
1339 register float *aa ;
1340
1341 dim = a.dim;
1342 sum = 0.0f;
1343 aa = a.elts ;
1344 for (i = 0; i < dim; i++)
1345 #if 0
1346 sum += a.elts[i] * a.elts[i];
1347 #else
1348 sum += aa[i] * aa[i] ;
1349 #endif
1350
1351 return (sum);
1352 }
1353
1354 /*---------------------------------------------------------------------------*/
1355 /*!
1356 Compute the L_infinity norm of a matrix: the max absolute row sum.
1357 */
1358
matrix_norm(matrix a)1359 float matrix_norm( matrix a )
1360 {
1361 int i,j , rows=a.rows, cols=a.cols ;
1362 float sum , smax=0.0f ;
1363
1364 for (i = 0; i < rows; i++){
1365 sum = 0.0f ;
1366 for (j = 0; j < cols; j++) sum += fabs(a.elts[i][j]) ;
1367 if( sum > smax ) smax = sum ;
1368 }
1369 return smax ;
1370 }
1371
1372 /*---------------------------------------------------------------------------*/
1373 /*! Search a matrix for nearly identical column pairs, where "nearly identical"
1374 means they are correlated closer than 1-eps.
1375
1376 Return is a pointer to an int array of the form
1377 [ i1 j1 i2 j2 ... -1 -1 ]
1378 where columns (i1,j1) are nearly the same, (i2,j2) also, etc.
1379 In addition:
1380 - A pair (i,-1) indicates that column #i is all zeros.
1381 - The array is terminated with the pair (-1,-1).
1382 - If there are no bad column pairs or all-zero columns, NULL is returned.
1383 - Pairs of all-zero columns are NOT reported.
1384 - The array should be free()-ed when you are done with it.
1385 -----------------------------------------------------------------------------*/
1386
matrix_check_columns(matrix a,double eps)1387 int * matrix_check_columns( matrix a , double eps )
1388 {
1389 int i,j,k , rows=a.rows , cols=a.cols ;
1390 int *iar=NULL , nar=0 ;
1391 double sumi,sumj,sumd ;
1392
1393 if( eps <= 0.0f ) eps = 1.e-5 ;
1394
1395 for( i=0 ; i < cols ; i++ ){
1396 sumi = 0.0 ;
1397 for( k=0 ; k < rows ; k++ ) sumi += a.elts[k][i] * a.elts[k][i] ;
1398 if( sumi <= 0.0 ){
1399 iar = (int *)realloc( (void *)iar , sizeof(int)*2*(nar+1) ) ;
1400 iar[2*nar] = i ; iar[2*nar+1] = -1 ; nar++ ;
1401 continue ; /* skip to next column i */
1402 }
1403 for( j=i+1 ; j < cols ; j++ ){
1404 sumj = sumd = 0.0 ;
1405 for( k=0 ; k < rows ; k++ ){
1406 sumj += a.elts[k][j] * a.elts[k][j] ;
1407 sumd += a.elts[k][j] * a.elts[k][i] ;
1408 }
1409 if( sumj > 0.0 ){
1410 sumd = fabs(sumd) / sqrt(sumi*sumj) ;
1411 if( sumd >= 1.0-eps ){
1412 iar = (int *)realloc( (void *)iar , sizeof(int)*2*(nar+1) ) ;
1413 iar[2*nar] = i ; iar[2*nar+1] = j ; nar++ ;
1414 }
1415 }
1416 }
1417 }
1418
1419 if( iar != NULL ){
1420 iar = (int *)realloc( (void *)iar , sizeof(int)*2*(nar+1) ) ;
1421 iar[2*nar] = iar[2*nar+1] = -1 ;
1422 }
1423
1424 return iar ;
1425 }
1426
1427 /*---------------------------------------------------------------------------*/
1428 /*! Return the eigenvalues of matrix X-transpose X.
1429 The output points to a vector of doubles, of length X.cols. This
1430 should be free()-ed when you are done with it.
1431 -----------------------------------------------------------------------------*/
1432
matrix_singvals(matrix X)1433 double * matrix_singvals( matrix X )
1434 {
1435 int i,j,k , M=X.rows , N=X.cols ;
1436 double *a , *e , sum ;
1437
1438 a = (double *) malloc( sizeof(double)*N*N ) ;
1439 e = (double *) malloc( sizeof(double)*N ) ;
1440
1441 for( i=0 ; i < N ; i++ ){
1442 for( j=0 ; j <= i ; j++ ){
1443 sum = 0.0 ;
1444 for( k=0 ; k < M ; k++ ) sum += X.elts[k][i] * X.elts[k][j] ;
1445 a[j+N*i] = sum ;
1446 if( j < i ) a[i+N*j] = sum ;
1447 }
1448 }
1449
1450 for( i=0 ; i < N ; i++ ){
1451 if( a[i+N*i] > 0.0 ) e[i] = 1.0 / sqrt(a[i+N*i]) ;
1452 else e[i] = 1.0 ;
1453 }
1454
1455 for( i=0 ; i < N ; i++ ){
1456 for( j=0 ; j < N ; j++ ) a[j+N*i] *= sqrt(e[i]*e[j]) ;
1457 }
1458
1459 symeigval_double( N , a , e ) ;
1460 free( (void *)a ) ;
1461 return e ;
1462 }
1463
1464 /*---------------------------------------------------------------------------*/
1465
1466 extern void svd_double( int, int, double *, double *, double *, double * ) ;
1467
1468 /*---------------------------------------------------------------------------*/
1469 /*! Given MxN matrix X, return the NxN matrix
1470
1471 [ T ]-1 [ T ]-1 T
1472 [ X X ] and the NxM matrix [ X X ] X
1473 -----------------------------------------------------------------------------*/
1474
matrix_psinv(matrix X,matrix * XtXinv,matrix * XtXinvXt)1475 void matrix_psinv( matrix X , matrix *XtXinv , matrix *XtXinvXt )
1476 {
1477 int m = X.rows , n = X.cols , ii,jj,kk ;
1478 double *amat , *umat , *vmat , *sval , *xfac , smax,del,sum ;
1479
1480 if( m < 1 || n < 1 || m < n || (XtXinv == NULL && XtXinvXt == NULL) ) return;
1481
1482 amat = (double *)calloc( sizeof(double),m*n ) ; /* input matrix */
1483 umat = (double *)calloc( sizeof(double),m*n ) ; /* left singular vectors */
1484 vmat = (double *)calloc( sizeof(double),n*n ) ; /* right singular vectors */
1485 sval = (double *)calloc( sizeof(double),n ) ; /* singular values */
1486 xfac = (double *)calloc( sizeof(double),n ) ; /* column norms of [a] */
1487
1488 #define A(i,j) amat[(i)+(j)*m]
1489 #define U(i,j) umat[(i)+(j)*m]
1490 #define V(i,j) vmat[(i)+(j)*n]
1491
1492 /* copy input matrix into amat */
1493
1494 for( ii=0 ; ii < m ; ii++ )
1495 for( jj=0 ; jj < n ; jj++ ) A(ii,jj) = X.elts[ii][jj] ;
1496
1497 /* scale each column to have norm 1 */
1498
1499 for( jj=0 ; jj < n ; jj++ ){
1500 sum = 0.0 ;
1501 for( ii=0 ; ii < m ; ii++ ) sum += A(ii,jj)*A(ii,jj) ;
1502 if( sum > 0.0 ) sum = 1.0/sqrt(sum) ;
1503 xfac[jj] = sum ;
1504 for( ii=0 ; ii < m ; ii++ ) A(ii,jj) *= sum ;
1505 }
1506
1507 /* compute SVD of scaled matrix */
1508
1509 svd_double( m , n , amat , sval , umat , vmat ) ;
1510
1511 free((void *)amat) ; /* done with this */
1512
1513 /* find largest singular value */
1514
1515 smax = sval[0] ;
1516 for( ii=1 ; ii < n ; ii++ )
1517 if( sval[ii] > smax ) smax = sval[ii] ;
1518
1519 if( smax <= 0.0 ){ /* this is bad */
1520 free((void *)xfac); free((void *)sval);
1521 free((void *)vmat); free((void *)umat); return;
1522 }
1523
1524 for( ii=0 ; ii < n ; ii++ )
1525 if( sval[ii] < 0.0 ) sval[ii] = 0.0 ;
1526
1527 #ifdef FLOATIZE
1528 #define PSINV_EPS 1.e-8
1529 #else
1530 #define PSINV_EPS 1.e-16
1531 #endif
1532
1533 /* "reciprocals" of singular values: 1/s is actually s/(s^2+del) */
1534
1535 del = PSINV_EPS * smax*smax ;
1536 for( ii=0 ; ii < n ; ii++ )
1537 sval[ii] = sval[ii] / ( sval[ii]*sval[ii] + del ) ;
1538
1539 /* create pseudo-inverse */
1540
1541 if( XtXinvXt != NULL ){
1542 matrix_create( n , m , XtXinvXt ) ;
1543 for( ii=0 ; ii < n ; ii++ ){
1544 for( jj=0 ; jj < m ; jj++ ){
1545 sum = 0.0 ;
1546 for( kk=0 ; kk < n ; kk++ )
1547 sum += sval[kk] * V(ii,kk) * U(jj,kk) ;
1548 XtXinvXt->elts[ii][jj] = sum * xfac[ii] ;
1549 }
1550 }
1551 }
1552
1553 if( XtXinv != NULL ){
1554 matrix_create( n , n , XtXinv ) ;
1555 for( ii=0 ; ii < n ; ii++ ) sval[ii] = sval[ii] * sval[ii] ;
1556 matrix_create( n , n , XtXinv ) ;
1557 for( ii=0 ; ii < n ; ii++ ){
1558 for( jj=0 ; jj < n ; jj++ ){
1559 sum = 0.0 ;
1560 for( kk=0 ; kk < n ; kk++ )
1561 sum += sval[kk] * V(ii,kk) * V(jj,kk) ;
1562 XtXinv->elts[ii][jj] = sum * xfac[ii] * xfac[jj] ;
1563 }
1564 }
1565 }
1566
1567 free((void *)xfac); free((void *)sval);
1568 free((void *)vmat); free((void *)umat); return;
1569 }
1570 /*---------------------------------------------------------------------------*/
1571 /*! Given MxN matrix X, compute the NxN upper triangle factor R in X = QR.
1572 Must have M >= N.
1573 Q is not computed. If you want Q, then compute it as [Q] = [X] * inv[R].
1574 *//*-------------------------------------------------------------------------*/
1575
matrix_qrr(matrix X,matrix * R)1576 int matrix_qrr( matrix X , matrix *R )
1577 {
1578 int m = X.rows , n = X.cols , ii,jj,kk ;
1579 float *amat , *uvec , x1 ;
1580 register float alp, sum ;
1581
1582 if( m < 2 || n < 1 || m < n || R == NULL || X.elts == NULL ) return -1 ;
1583
1584 #undef A
1585 #define A(i,j) amat[(i)+(j)*m]
1586
1587 amat = (float *)malloc( sizeof(float)*m*n ) ; /* copy input matrix */
1588 uvec = (float *)malloc( sizeof(float)*m ) ; /* Householder vector */
1589
1590 /* copy input matrix into amat == A */
1591
1592 for( ii=0 ; ii < m ; ii++ )
1593 for( jj=0 ; jj < n ; jj++ ) A(ii,jj) = X.elts[ii][jj] ;
1594
1595 /* Householder transform each column of A in turn */
1596
1597 for( jj=0 ; jj < n ; jj++ ){
1598 if( jj == m-1 ) break ; /* at last column AND have m==n */
1599 x1 = uvec[jj] = A(jj,jj) ;
1600 for( sum=0.0f,ii=jj+1 ; ii < m ; ii++ ){
1601 uvec[ii] = alp = A(ii,jj) ; sum += alp*alp ;
1602 }
1603 if( sum == 0.0f ) continue ; /* tail of column is pre-reduced to 0 */
1604 alp = sqrtf(sum+x1*x1) ; if( x1 > 0.0f ) alp = -alp ;
1605 x1 = uvec[jj] -= alp ; A(jj,jj) = alp ;
1606 alp = 2.0f / (sum+x1*x1) ;
1607 for( kk=jj+1 ; kk < n ; kk++ ){ /* process trailing columns */
1608 for( sum=0.0,ii=jj ; ii < m ; ii++ ) sum += uvec[ii]*A(ii,kk) ;
1609 sum *= alp ;
1610 for( ii=jj ; ii < m ; ii++ ) A(ii,kk) -= sum*uvec[ii] ;
1611 }
1612 }
1613 /* copy result in A to output
1614 (changing row signs if needed to make R's diagonal non-negative) */
1615
1616 matrix_create( n , n , R ) ;
1617 for( ii=0 ; ii < n ; ii++ ){
1618 for( jj=0 ; jj < ii ; jj++ ) R->elts[ii][jj] = 0.0 ; /* sub-diagonal */
1619 if( A(ii,ii) >= 0.0f )
1620 for( jj=ii ; jj < n ; jj++ ) R->elts[ii][jj] = A(ii,jj) ;
1621 else
1622 for( jj=ii ; jj < n ; jj++ ) R->elts[ii][jj] = -A(ii,jj) ;
1623 }
1624
1625 free((void *)uvec) ; free((void *)amat) ;
1626 return 0 ;
1627 }
1628
1629 /*---------------------------------------------------------------------------*/
1630 /*! Solve [R] [x] = [b] for [x] where R is upper triangular. */
1631
vector_rr_solve(matrix R,vector b,vector * x)1632 void vector_rr_solve( matrix R , vector b , vector *x )
1633 {
1634 register int n , ii,jj ;
1635 register float sum , *xp ;
1636
1637 n = R.rows ;
1638 if( n < 1 || R.cols != n || x == NULL ) return ;
1639
1640 vector_create_noinit( n , x ) ; xp = x->elts ;
1641
1642 for( ii=n-1 ; ii >= 0 ; ii-- ){
1643 for( sum=b.elts[ii],jj=ii+1 ; jj < n ; jj++ )
1644 sum -= R.elts[ii][jj] * xp[jj] ;
1645 xp[ii] = sum / R.elts[ii][ii] ;
1646 }
1647
1648 return ;
1649 }
1650
1651 /*---------------------------------------------------------------------------*/
1652 /*! Solve [R]' [x] = [b] for [x] where R is upper triangular. */
1653
vector_rrtran_solve(matrix R,vector b,vector * x)1654 void vector_rrtran_solve( matrix R , vector b , vector *x )
1655 {
1656 register int n , ii,jj ;
1657 register float sum , *xp ;
1658
1659 n = R.rows ;
1660 if( n < 1 || R.cols != n || x == NULL ) return ;
1661
1662 vector_create_noinit( n , x ) ; xp = x->elts ;
1663
1664 for( ii=0 ; ii < n ; ii++ ){
1665 for( sum=b.elts[ii],jj=0 ; jj < ii ; jj++ )
1666 sum -= R.elts[jj][ii] * xp[jj] ;
1667 xp[ii] = sum / R.elts[ii][ii] ;
1668 }
1669
1670 return ;
1671 }
1672