Debian Codegraph @

lib/external/ccmath/C01-matrix

raw
1 Chapter 1
2
3 LINEAR ALGEBRA
4
5 Summary
6
7 The matrix algebra library contains functions that
8 perform the standard computations of linear algebra.
9 General areas covered are:
10
11 o Solution of Linear Systems
12 o Matrix Inversion
13 o Eigensystem Analysis
14 o Matrix Utility Operations
15 o Singular Value Decomposition
16
17 The operations covered here are fundamental to many
18 areas of mathematics and statistics. Thus, functions
19 in this library segment are called by other library
20 functions. Both real and complex valued matrices
21 are covered by functions in the first four of these
22 categories.
23
24
25 Notes on Contents
26
27 Functions in this library segment provide the basic operations of
28 numerical linear algebra and some useful utility functions for operations on
29 vectors and matrices. The following list describes the functions available for
30 operations with real-valued matrices.
31
32
33 o Solving and Inverting Linear Systems:
34
35 solv --------- solve a general system of real linear equations.
36 solvps ------- solve a real symmetric linear system.
37 solvru ------- solve a real right upper triangular linear system.
38 solvtd ------- solve a tridiagonal real linear system.
39
40 minv --------- invert a general real square matrix.
41 psinv -------- invert a real symmetric matrix.
42 ruinv -------- invert a right upper triangular matrix.
43
44
45 The solution of a general linear system and efficient algorithms for
46 solving special systems with symmetric and tridiagonal matrices are provided
47 by these functions. The general solution function employs a LU factorization
48 with partial pivoting and it is very robust. It will work efficiently on any
49 problem that is not ill-conditioned. The symmetric matrix solution is based
50 on a modified Cholesky factorization. It is best used on positive definite
51 matrices that do not require pivoting for numeric stability. Tridiagonal
52 solvers require order-N operations (N = dimension). Thus, they are highly
53 recommended for this important class of sparse systems. Two matrix inversion
54 routines are provided. The general inversion function is again LU based. It
55 is suitable for use on any stable (ie. well-conditioned) problem. The
56 Cholesky based symmetric matrix inversion is efficient and safe for use on
57 matrices known to be positive definite, such as the variance matrices
58 encountered in statistical computations. Both the solver and the inverse
59 functions are designed to enhance data locality. They are very effective
60 on modern microprocessors.
61
62
63 o Eigensystem Analysis:
64
65 eigen ------ extract all eigen values and vectors of a real
66 symmetric matrix.
67 eigval ----- extract the eigen values of a real symmetric matrix.
68 evmax ------ compute the eigen value of maximum absolute magnitude
69 and its corresponding vector for a symmetric matrix.
70
71
72 Eigensystem functions operate on real symmetric matrices. Two forms of
73 the general eigen routine are provided because the computation of eigen values
74 only is much faster when vectors are not required. The basic algorithms use
75 a Householder reduction to tridiagonal form followed by QR iterations with
76 shifts to enhance convergence. This has become the accepted standard for
77 symmetric eigensystem computation. The evmax function uses an efficient
78 iterative power method algorithm to extract the eigen value of maximum
79 absolute size and the corresponding eigenvector.
80
81
82 o Singular Value Decomposition:
83
84 svdval ----- compute the singular values of a m by n real matrix.
85 sv2val ----- compute the singular values of a real matrix
86 efficiently for m >> n.
87 svduv ------ compute the singular values and the transformation
88 matrices u and v for a real m by n matrix.
89 sv2uv ------ compute the singular values and transformation
90 matrices efficiently for m >> n.
91 svdu1v ----- compute the singular values and transformation
92 matrices u1 and v, where u1 overloads the input
93 with the first n column vectors of u.
94 sv2u1v ----- compute the singular values and the transformation
95 matrices u1 and v efficiently for m >> n.
96
97
98 Singular value decomposition is extremely useful when dealing with linear
99 systems that may be singular. Singular values with values near zero are flags
100 of a potential rank deficiency in the system matrix. They can be used to
101 identify the presence of an ill-conditioned problem and, in some cases, to
102 deal with the potential instability. They are applied to the linear least
103 squares problem in this library. Singular values also define some important
104 matrix norm parameters such as the 2-norm and the condition value. A complete
105 decomposition provides both singular values and an orthogonal decomposition of
106 vector spaces related to the matrix identifying the range and null-space.
107 Fortunately, a highly stable algorithm based on Householder reduction to
108 bidiagonal form and QR rotations can be used to implement the decomposition.
109 The library provides two forms with one more efficient when the dimensions
110 satisfy m > (3/2)n.
111
112
113 o Real Matrix Utilities:
114
115 rmmult ----- multiply two compatible real matrices.
116 mmul ------- multiply two real square matrices.
117 vmul ------- multiply a vector by a square matrix (transform).
118 mattr ------ compute the transpose of a general matrix.
119 trnm ------- transpose a real square matrix in place.
120 otrma ------ compute orthogonal conjugate of a square matrix.
121 otrsm ------ compute orthogonal conjugate of a symmetric matrix.
122 smgen ------ construct a symmetric matrix from its eigen values
123 and vectors.
124 ortho ------ generate a general orthogonal matrix (uses random
125 rotation generator).
126 mcopy ------ make a copy of an array.
127 matprt ----- print a matrix in row order with a specified
128 format for elements to stdout or a file (fmatprt).
129
130
131 The utility functions perform simple matrix operations such as matrix
132 multiplication, transposition, matrix conjugation, and linear transformation
133 of a vector. They are used to facilitate the rapid production of test and
134 application code requiring these operations. The function call overhead
135 associated with use of these utilities becomes negligible as the dimension of
136 the matrices increases. The implementation of these routines is designed to
137 enhance data locality and thus execution performance. A generator for
138 orthogonal matrices can be used to generate test matrices.
139
140
141 Linear Algebra with Complex Matrices
142
143 The complex section of the linear algebra library contains functions that
144 operate on general complex valued matrices and on Hermitian matrices.
145 Hermitian matrices are the complex analog of symmetric matrices. Complex
146 arithmetic is performed in-line in these functions to ensure efficient
147 execution.
148
149
150 o Solving and Inverting Complex Linear Systems:
151
152 csolv ------ solve a general complex system of linear equations.
153
154 cminv ------ invert a general complex matrix.
155
156
157 Both these functions are based on the robust LU factorization algorithm
158 with row pivots. They can be expected to solve or invert any system that is
159 well conditioned.
160
161
162 o Hermitian Eigensystem Analysis:
163
164 heigvec ---- extract the eigen values and vectors of a Hermitian
165 matrix.
166 heigval ---- compute the eigenvalues of a Hermitian matrix.
167 hevmax ----- compute the eigen value of largest absolute magnitude
168 and the corresponding vector of a Hermitian matrix.
169
170
171 The algorithms used for complex eigensystems are complex generalizations
172 of those employed in the real systems. The eigen values of Hermitian matrices
173 are real and their eigenvectors form a unitary matrix. As in the real case,
174 the function for eigen values only is provided as a time saver. These
175 routines have important application to many quantum mechanical problems.
176
177
178 o Complex Matrix Utilities:
179
180 cmmult ---- multiply two general, size compatible, complex matrices.
181 cmmul ----- multiply two square complex matrices.
182 cvmul ----- multiply a complex vector by a complex square matrix.
183 cmattr ---- transpose a general complex matrix.
184 trncm ----- transpose a complex square matrix in place.
185 hconj ----- transform a square complex matrix to its Hermitian
186 conjugate in place.
187 utrncm ---- compute the unitary transform of a complex matrix.
188 utrnhm ---- compute the unitary transform of a Hermitian matrix.
189 hmgen ----- generate a general Hermitian from its eigen values
190 and vectors.
191 unitary --- generate a general unitary matrix (uses a random
192 rotation generator).
193 cmcpy ----- copy a complex array.
194 cmprt ----- print a complex matrix in row order with a specified
195 format for matrix elements.
196
197
198 These utility operations replicate the utilities available for real
199 matrices. Matrix computations implemented in a manner that enhances data
200 locality. This ensures their efficiency on modern computers with a memory
201 hierarchy.
202
203 -------------------------------------------------------------------------------
204
205 General Technical Comments
206
207 Efficient computation with matrices on modern processors must be
208 adapted to the storage scheme employed for matrix elements. The functions
209 of this library segment do not employ the multidimensional array intrinsic
210 of the C language. Access to elements employs the simple row-major scheme
211 described here.
212
213 Matrices are modeled by the library functions as arrays with elements
214 stored in row order. Thus, the element in the jth row and kth column of
215 the n by n matrix M, stored in the array mat[], is addressed by
216
217 M[j,k] = mat[n*j+k] , with 0 =< j,k <= n-1 .
218
219 (Remember that C employs zero as the starting index.) The storage order has
220 important implications for data locality.
221
222 The algorithms employed here all have excellent numerical stability, and
223 the default double precision arithmetic of C enhances this. Thus, any
224 problems encountered in using the matrix algebra functions will almost
225 certainly be due to an ill-conditioned matrix. (The Hilbert matrices,
226
227 H[i,j] = 1/(1+i+j) for i,j < n
228
229 form a good example of such ill-conditioned systems.) We remind the reader
230 that the appropriate response to such ill-conditioning is to seek an
231 alternative approach to the problem. The option of increasing precision has
232 already been exploited. Modification of the linear algebra algorithm code is
233 not normally effective in an ill-conditioned problem.
234
235 ------------------------------------------------------------------------------
236 FUNCTION SYNOPSES
237 ------------------------------------------------------------------------------
238
239 Linear System Solutions:
240 -----------------------------------------------------------------------------
241
242 solv
243
244 Solve a general linear system A*x = b.
245
246 int solv(double a[],double b[],int n)
247 a = array containing system matrix A in row order
248 (altered to L-U factored form by computation)
249 b = array containing system vector b at entry and
250 solution vector x at exit
251 n = dimension of system
252 return: 0 -> normal exit
253 -1 -> singular input
254
255 -----------------------------------------------------------
256
257 solvps
258
259 Solve a symmetric positive definite linear system S*x = b.
260
261 int solvps(double a[],double b[],int n)
262 a = array containing system matrix S (altered to
263 Cholesky upper right factor by computation)
264 b = array containing system vector b as input and
265 solution vector x as output
266 n = dimension of system
267 return: 0 -> normal exit
268 1 -> input matrix not positive definite
269
270 --------------------------------------------------------------
271
272 solvtd
273
274 Solve a tridiagonal linear system M*x = y.
275
276 void solvtd(double a[],double b[],double c[],double x[],int m)
277 a = array containing m+1 diagonal elements of M
278 b = array of m elements below the main diagonal of M
279 c = array of m elements above the main diagonal
280 x = array containing the system vector y initially, and
281 the solution vector at exit (m+1 elements)
282 m = dimension parameter ( M is (m+1)x(m+1) )
283
284 --------------------------------------------------------------
285
286 solvru
287
288 Solve an upper right triangular linear system T*x = b.
289
290 int solvru(double *a,double *b,int n)
291 a = pointer to array of upper right triangular matrix T
292 b = pointer to array of system vector
293 The computation overloads this with the
294 solution vector x.
295 n = dimension (dim(a)=n*n,dim(b)=n)
296 return value: f = status flag, with 0 -> normal exit
297 -1 -> system singular
298
299 ------------------------------------------------------------------------------
300
301 Matrix Inversion:
302 ------------------------------------------------------------------------------
303
304 minv
305
306 Invert (in place) a general real matrix A -> Inv(A).
307
308 int minv(double a[],int n)
309 a = array containing the input matrix A
310 This is converted to the inverse matrix.
311 n = dimension of the system (i.e. A is n x n )
312 return: 0 -> normal exit
313 1 -> singular input matrix
314
315 --------------------------------------------------------------
316
317 psinv
318
319 Invert (in place) a symmetric real matrix, V -> Inv(V).
320
321 int psinv(double v[],int n)
322 v = array containing a symmetric input matrix
323 This is converted to the inverse matrix.
324 n = dimension of the system (dim(v)=n*n)
325 return: 0 -> normal exit
326 1 -> input matrix not positive definite
327
328 The input matrix V is symmetric (V[i,j] = V[j,i]).
329
330 --------------------------------------------------------------
331
332 ruinv
333
334 Invert an upper right triangular matrix T -> Inv(T).
335
336 int ruinv(double *a,int n)
337 a = pointer to array of upper right triangular matrix
338 This is replaced by the inverse matrix.
339 n = dimension (dim(a)=n*n)
340 return value: status flag, with 0 -> matrix inverted
341 -1 -> matrix singular
342
343
344 -----------------------------------------------------------------------------
345
346 Symmetric Eigensystem Analysis:
347 -----------------------------------------------------------------------------
348
349 eigval
350
351 Compute the eigenvalues of a real symmetric matrix A.
352
353 void eigval(double *a,double *ev,int n)
354 a = pointer to array of symmetric n by n input
355 matrix A. The computation alters these values.
356 ev = pointer to array of the output eigenvalues
357 n = dimension parameter (dim(a)= n*n, dim(ev)= n)
358
359 --------------------------------------------------------------
360
361 eigen
362
363 Compute the eigenvalues and eigenvectors of a real symmetric
364 matrix A.
365
366 void eigen(double *a,double *ev,int n)
367 double *a,*ev; int n;
368 a = pointer to store for symmetric n by n input
369 matrix A. The computation overloads this with an
370 orthogonal matrix of eigenvectors E.
371 ev = pointer to the array of the output eigenvalues
372 n = dimension parameter (dim(a)= n*n, dim(ev)= n)
373
374 The input and output matrices are related by
375
376 A = E*D*E~ where D is the diagonal matrix of eigenvalues
377 D[i,j] = ev[i] if i=j and 0 otherwise.
378
379 The columns of E are the eigenvectors.
380
381 ---------------------------------------------------------------
382
383 evmax
384
385 Compute the maximum (absolute) eigenvalue and corresponding
386 eigenvector of a real symmetric matrix A.
387
388 double evmax(double a[],double u[],int n)
389 double a[],u[]; int n;
390 a = array containing symmetric input matrix A
391 u = array containing the n components of the eigenvector
392 at exit (vector normalized to 1)
393 n = dimension of system
394 return: ev = eigenvalue of A with maximum absolute value
395 HUGE -> convergence failure
396
397
398 -----------------------------------------------------------------------------
399 Eigensystem Auxiliaries:
400 -----------------------------------------------------------------------------
401
402 The following routines are used by the eigensystem functions.
403 They are not normally called by the user.
404
405 house
406
407 Transform a real symmetric matrix to tridiagonal form.
408
409 void house(double *a,double *d,double *dp,int n)
410 a = pointer to array of the symmetric input matrix A
411 These values are altered by the computation.
412 d = pointer to array of output diagonal elements
413 dp = pointer to array of n-1 elements neighboring the
414 diagonal in the symmetric transformed matrix
415 n = dimension (dim(a)= n*n, dim(d)=dim(dp)=n)
416
417 The output arrays are related to the tridiagonal matrix T by
418
419 T[i,i+1] = T[i+1,i] = dp[i] for i=0 to n-2, and
420 T[i,i] = d[i] for i=0 to n-1.
421 --------------------------------------------------------------
422
423 housev
424
425 Transform a real symmetric matrix to tridiagonal form and
426 compute the orthogonal matrix of this transformation.
427
428 void housev(double *a,double *d,double *dp,int n)
429 a = pointer to array of symmetric input matrix A
430 The computation overloads this array with the
431 orthogonal transformation matrix O.
432 d = pointer to array of diagonal output elements
433 dp = pointer to array of n-1 elements neighboring the
434 diagonal in the symmetric transformed matrix
435 n = dimension (dim(a)= n*n, dim(d)=dim(dp)=n)
436
437 The orthogonal transformation matrix O satisfies O~*T*O = A.
438 ----------------------------------------------------------------
439
440 qreval
441
442 Perform a QR reduction of a real symmetric tridiagonal
443 matrix to diagonal form.
444
445 int qreval(double *ev,double *dp,int n)
446 ev = pointer to array of input diagonal elements
447 The computation overloads this array with
448 eigenvalues.
449 dp = pointer to array input elements neighboring the
450 diagonal. This array is altered by the computation.
451 n = dimension (dim(ev)=dim(dp)= n)
452
453 ---------------------------------------------------------------
454
455 qrevec
456
457 Perform a QR reduction of a real symmetric tridiagonal matrix
458 to diagonal form and update an orthogonal transformation matrix.
459
460 int qrevec(double *ev,double *evec,double *dp,int n)
461 ev = pointer to array of input diagonal elements
462 that the computation overloads with eigenvalues
463 evec = pointer array of orthogonal input matrix
464 This is updated by the computation to a matrix
465 of eigenvectors.
466 dp = pointer to array input elements neighboring the
467 diagonal. This array is altered by the computation.
468 n = dimension (dim(ev)=dim(dp)= n)
469
470 This function operates on the output of 'housev'.
471
472 ------------------------------------------------------------------------------
473
474 Matrix Utilities:
475 ------------------------------------------------------------------------------
476
477 mmul
478
479 Multiply two real square matrices C = A * B.
480
481 void mmul(double *c,double *a,double *b,int n)
482 double *a,*b,*c; int n;
483 a = pointer to store for left product matrix
484 b = pointer to store for right product matrix
485 c = pointer to store for output matrix
486 n = dimension (dim(a)=dim(b)=dim(c)=n*n)
487
488 -------------------------------------------------------
489
490 rmmult
491
492 Multiply two matrices Mat = A*B.
493
494 void rmmult(double *mat,double *a,double *b,int m,int k,int n)
495 double mat[],a[],b[]; int m,k,n;
496 mat = array containing m by n product matrix at exit
497 a = input array containing m by k matrix
498 b = input array containing k by n matrix
499 (all matrices stored in row order)
500 m,k,n = dimension parameters of arrays
501
502 ----------------------------------------------------------
503
504 vmul
505
506 Multiply a vector by a matrix Vp = Mat*V.
507
508 void vmul(double *vp,double *mat,double *v,int n)
509 vp = pointer to array containing output vector
510 mat = pointer to array containing input matrix in row order
511 v = pointer to array containing input vector
512 n = dimension of vectors (mat is n by n)
513
514 ----------------------------------------------------------------
515
516 vnrm
517
518 Compute the inner product of two real vectors, p = u~*v.
519
520 double vnrm(double *u,double *v,int n)
521 u = pointer to array of input vector u
522 v = pointer to array of input vector v
523 n = dimension (dim(u)=dim(v)=n)
524 return value: p = u~*v (dot product of u and v)
525
526 -----------------------------------------------------
527
528 trnm
529
530 Transpose a real square matrix in place A -> A~.
531
532 void trnm(double *a,int n)
533 a = pointer to array of n by n input matrix A
534 This is overloaded by the transpose of A.
535 n = dimension (dim(a)=n*n)
536
537 ---------------------------------------------------------
538
539 mattr
540
541 Transpose an m by n matrix A = B~.
542
543 void mattr(double *a,double *b,int m,int n)
544 a = pointer to array containing output n by m matrix
545 b = pointer to array containing input m by n matrix
546 (matrices stored in row order)
547 m,n = dimension parameters (dim(a)=dim(b)=n*m)
548
549 ------------------------------------------------------------
550
551 otrma
552
553 Perform an orthogonal similarity transform C = A*B*A~.
554
555 void otrma(double *c,double *a,double *b,int n)
556 c = pointer to array of output matrix C
557 a = pointer to array of transformation A
558 b = pointer to array of input matrix B
559 n = dimension (dim(a)=dim(b)=dim(c)=n*n)
560
561 -----------------------------------------------------------
562
563 otrsm
564
565 Perform a similarity transform on a symmetric matrix S = A*B*A~.
566
567 void otrsm(double *sm,double *a,double *b,int n)
568 sm = pointer to array of output matrix S
569 a = pointer to array of transformation matrix A
570 b = pointer to array of symmetric input matrix B
571 n = dimension (dim(a)=dim(b)=dim(sm)=n*n)
572
573 ---------------------------------------------------------------
574
575 smgen
576
577 Construct a symmetric matrix from specified eigenvalues and
578 eigenvectors.
579
580 void smgen(double *a,double *eval,double *evec,int n)
581 a = pointer to array containing output matrix
582 eval = pointer to array containing the n eigenvalues
583 evec = pointer to array containing eigenvectors
584 (n by n with kth column the vector corresponding
585 to the kth eigenvalue)
586 n = system dimension
587
588 If D is the diagonal matrix of eigenvalues
589 and E[i,j] = evec[j+n*i] , then A = E*D*E~.
590
591 ----------------------------------------------------------------
592
593 ortho
594
595 Generate a general orthogonal transformation matrix, E~*E = I.
596
597 void ortho(double *e,int n)
598 e = pointer to array of orthogonal output matrix E
599 n = dimension of vector space (dim(e)=n*n)
600
601 This function calls on the uniform random generator 'unfl' to
602 produce random rotation angles. Therefore this random generator
603 should be initialized by a call of 'setunfl' before calling
604 ortho (see Chapter 7).
605
606 -----------------------------------------------------------------
607
608 mcopy
609
610 Copy an array a = b.
611
612 void mcopy(double *a,double *b,int n)
613 a = array containing output values, identical to input
614 b at exit
615 b = input array
616 n = dimension of arrays
617
618 -----------------------------------------------------------
619
620 matprt
621
622 Print an array in n rows of m columns to stdout.
623
624 void matprt(double *a,int n,int m,char *fmt)
625 a = pointer to input array stored in row order (size = n*m)
626 n = number of output rows
627 m = number of output columns
628 fmt= pointer to character array containing format string
629 (printf formats eg. " %f")
630
631 Long rows may overflow the print line.
632
633 ---------------------------------------------------------------
634
635 fmatprt
636
637 Print formatted array output to a file.
638
639 void fmatprt(FILE *fp,double *a,int n,int m,char *fmt)
640 fp = pointer to file opened for writing
641 a = pointer to input array stored in row order (size = n*m)
642 n = number of output rows
643 m = number of output columns
644 fmt= pounter to character array containing format string
645 (printf formats eg. " %f")
646
647 ------------------------------------------------------------------------------
648
649 Singular Value Decomposition:
650 ------------------------------------------------------------------------------
651
652 A number of versions of the Singular Value Decomposition (SVD)
653 are implemented in the library. They support the efficient
654 computation of this important factorization for a real m by n
655 matrix A. The general form of the SVD is
656
657 A = U*S*V~ with S = | D |
658 | 0 |
659
660 where U is an m by m orthogonal matrix, V is an n by n orthogonal matrix,
661 D is the n by n diagonal matrix of singular value, and S is the singular
662 m by n matrix produced by the transformation.
663
664 The singular values computed by these functions provide important
665 information on the rank of the matrix A, and on several matrix
666 norms of A. The number of non-zero singular values d[i] in D
667 equal to the rank of A. The two norm of A is
668
669 ||A|| = max(d[i]) , and the condition number is
670
671 k(A) = max(d[i])/min(d[i]) .
672
673 The Frobenius norm of the matrix A is
674
675 Fn(A) = Sum(i=0 to n-1) d[i]^2 .
676
677 Singular values consistent with zero are easily recognized, since
678 the decomposition algorithms have excellent numerical stability.
679 The value of a 'zero' d[i] is no larger than a few times the
680 computational rounding error e.
681
682 The matrix U1 is formed from the first n orthonormal column vectors
683 of U. U1[i,j] = U[i,j] for i = 1 to m and j = 1 to n. A singular
684 value decomposition of A can also be expressed in terms of the m by\
685 n matrix U1, with
686
687 A = U1*D*V~ .
688
689 SVD functions with three forms of output are provided. The first
690 form computes only the singular values, while the second computes
691 the singular values and the U and V orthogonal transformation
692 matrices. The third form of output computes singular values, the
693 V matrix, and saves space by overloading the input array with
694 the U1 matrix.
695
696 Two forms of decomposition algorithm are available for each of the
697 three output types. One is computationally efficient when m ~ n.
698 The second, distinguished by the prefix 'sv2' in the function name,
699 employs a two stage Householder reduction to accelerate computation
700 when m substantially exceeds n. Use of functions of the second form
701 is recommended for m > 2n.
702
703 Singular value output from each of the six SVD functions satisfies
704
705 d[i] >= 0 for i = 0 to n-1.
706 -------------------------------------------------------------------------------
707
708 svdval
709
710 Compute the singular values of a real m by n matrix A.
711
712 int svdval(double *d,double *a,int m,int n)
713 d = pointer to double array of dimension n
714 (output = singular values of A)
715 a = pointer to store of the m by n input matrix A
716 (A is altered by the computation)
717 m = number of rows in A
718 n = number of columns in A (m>=n required)
719 return value: status flag with:
720 0 -> success
721 -1 -> input error m < n
722
723 ------------------------------------------------------------
724
725 sv2val
726
727 Compute singular values when m >> n.
728
729 int sv2val(double *d,double *a,int m,int n)
730 d = pointer to double array of dimension n
731 (output = singular values of A)
732 a = pointer to store of the m by n input matrix A
733 (A is altered by the computation)
734 m = number of rows in A
735 n = number of columns in A (m>=n required)
736 return value: status flag with:
737 0 -> success
738 -1 -> input error m < n
739 --------------------------------------------------------------
740
741 svduv
742
743 Compute the singular value transformation S = U~*A*V.
744
745 int svduv(double *d,double *a,double *u,int m,double *v,int n)
746 d = pointer to double array of dimension n
747 (output = singular values of A)
748 a = pointer to store of the m by n input matrix A
749 (A is altered by the computation)
750 u = pointer to store for m by m orthogonal matrix U
751 v = pointer to store for n by n orthogonal matrix V
752 m = number of rows in A
753 n = number of columns in A (m>=n required)
754 return value: status flag with:
755 0 -> success
756 -1 -> input error m < n
757
758 --------------------------------------------------------------------
759
760 sv2uv
761
762 Compute the singular value transformation when m >> n.
763
764 int sv2uv(double *d,double *a,double *u,int m,double *v,int n)
765 d = pointer to double array of dimension n
766 (output = singular values of A)
767 a = pointer to store of the m by n input matrix A
768 (A is altered by the computation)
769 u = pointer to store for m by m orthogonal matrix U
770 v = pointer to store for n by n orthogonal matrix V
771 m = number of rows in A
772 n = number of columns in A (m>=n required)
773 return value: status flag with:
774 0 -> success
775 -1 -> input error m < n
776
777 ----------------------------------------------------------------
778
779 svdu1v
780
781 Compute the singular value transformation with A overloaded by
782 the partial U-matrix.
783
784 int svdu1v(double *d,double *a,int m,double *v,int n)
785 d = pointer to double array of dimension n
786 (output = singular values of A)
787 a = pointer to store of the m by n input matrix A
788 (At output a is overloaded by the matrix U1
789 whose n columns are orthogonal vectors equal to
790 the first n columns of U.)
791 v = pointer to store for n by n orthogonal matrix V
792 m = number of rows in A
793 n = number of columns in A (m>=n required)
794 return value: status flag with:
795 0 -> success
796 -1 -> input error m < n
797
798 ------------------------------------------------------------------
799
800 sv2u1v
801
802 Compute the singular value transformation with partial U
803 matrix U1 efficiently for m >> n.
804
805 #include <math.h>
806 int sv2u1v(d,a,m,v,n)
807 double *d,*a,*v; int m,n;
808 d = pointer to double array of dimension n
809 (output = singular values of A)
810 a = pointer to store of the m by n input matrix A
811 (At output a is overloaded by the matrix U1
812 whose n columns are orthogonal vectors equal to
813 the first n columns of U.)
814 v = pointer to store for n by n orthogonal matrix V
815 m = number of rows in A
816 n = number of columns in A (m>=n required)
817 return value: status flag with:
818 0 -> success
819 -1 -> input error m < n
820
821 -------------------------------------------------------------------------------
822 Auxiliary Functions used in SVD Computation:
823 -------------------------------------------------------------------------------
824
825 The following routines are used by the singular value decomposition
826 functions. They are not normally called by the user.
827
828 qrbdi
829
830 Perform a QR reduction of a bidiagonal matrix.
831
832 int qrbdi(double *d,double *e,int m)
833 d = pointer to n-dimensional array of diagonal values
834 (overloaded by diagonal elements of reduced matrix)
835 e = pointer to store of superdiagonal values (loaded in
836 first m-1 elements of the array). Values are altered
837 by the computation.
838 m = dimension of the d and e arrays
839 return value: N = number of QR iterations required
840
841 -------------------------------------------------------------
842
843 qrbdv
844
845 Perform a QR reduction of a bidiagonal matrix and update the
846 the orthogonal transformation matrices U and V.
847
848 int qrbdv(double *d,double *e,double *u,int m,double *v,int n)
849 d = pointer to n-dimensional array of diagonal values
850 (overloaded by diagonal elements of reduced matrix)
851 e = pointer to store of superdiagonal values (loaded in
852 first m-1 elements of the array). Values are altered
853 by the computation.
854 u = pointer to store of m by m orthogonal matrix U updated
855 by the computation
856 v = pointer to store of n by n orthogonal matrix V updated
857 by the computation
858 m = dimension parameter of the U matrix
859 n = size of the d and e arrays and the number of rows and
860 columns in the V matrix
861 return value: N = number of QR iterations required
862
863 ---------------------------------------------------------------
864
865 qrbd1
866
867 Perform a QR reduction of a bidiagonal matrix and update the
868 transformation matrices U1 and V.
869
870 int qrbdu1(double *d,double *e,double *u1,int m,double *v,int n)
871 d = pointer to n-dimensional array of diagonal values
872 (overloaded by diagonal elements of reduced matrix)
873 e = pointer to store of superdiagonal values (loaded in
874 first m-1 elements of the array). Values are altered
875 by the computation.
876 u1 = pointer to store of m by n transformation matrix U1
877 updated by the computation
878 v = pointer to store of n by n orthogonal matrix V updated
879 by the computation
880 m = number of rows in the U1 matrix
881 n = size of the d and e arrays, number of columns in the U1
882 matrix, and the number of rows and columns in the V matrix.
883 return value: N = number of QR iterations required
884
885 ------------------------------------------------------------------
886
887 ldumat
888
889 Compute a left Householder transform matrix U from the vectors
890 specifying the Householder reflections.
891
892 void ldumat(double *a,double *u,int m,int n)
893 a = pointer to store of m by n input matrix A. Elements
894 of A on and below the main diagonal specify the
895 vectors of n Householder reflections (see note below).
896 u = pointer to store for the m by m orthogonal output
897 matrix U.
898 m = number of rows in A and U, and number of columns in U.
899 n = number of columns in A
900
901 --------------------------------------------------------------
902
903 ldvmat
904
905 Compute a right Householder transform matrix from the vectors
906 specifying the Householder reflections.
907
908 void ldvmat(double *a,double *v,int n)
909 a = pointer to store of n by n input matrix A. Elements
910 of A on and above the superdiagonal specify vectors
911 of a sequence of Householder reflections (see note below).
912 v = pointer to store for the n by n orthogonal output
913 matrix V
914 n = number of rows and columns in A and V
915
916 -----------------------------------------------------------------
917
918 atou1
919
920 Overload a Householder left-factored matrix A with the first
921 n columns of the Householder orthogonal matrix.
922
923 void atou1(double *a,int m,int n)
924 a = pointer to store of m by n input matrix A. Elements
925 of A on and below the main diagonal specify the
926 vectors of n Householder reflections (see note below).
927 This array is overloaded by the first n columns of the
928 Householder transformation matrix.
929 m = number of rows in A
930 n = number of columns in A
931
932 ---------------------------------------------------------------
933
934 atovm
935
936 Overload a Householder right-factored square matrix A with the
937 Householder transformation matrix V.
938
939 void atovm(double *v,int n)
940 v = pointer to store for the n by n orthogonal
941 output matrix V
942 n = number of rows and columns in V
943
944 -------------------------------------------------------------------------------
945
946 Individual Householder reflections are specified by a vector h.
947 The corresponding orthogonal reflection matrix is given by
948
949 H = I - c* h~ .
950
951 Input matrices store the vector, normalized to have its leading
952 coefficient equal to one, and the normalization factor
953
954 c = 2/(h~*h) .
955
956 Storage for the vectors is by column starting at the diagonal for
957 a left transform, and by row starting at the superdiagonal for a
958 right transform. The first location holds c followed by
959 components 2 to k of the vector.
960
961
962 -------------------------------------------------------------------------------
963 Complex Linear Algebra
964 -------------------------------------------------------------------------------
965
966 Solution and Inverse:
967 -------------------------------------------------------------------------------
968
969 csolv
970
971 Solve a complex linear system A*x = b.
972
973 int csolv(Cpx *a,Cpx *b,int n)
974 a = pointer to array of n by n system matrix A
975 The computation alters this array to a LU factorization.
976 b = pointer to input array of system vector b
977 This is replaced by the solution vector b -> x.
978 n = dimension of system (dim(a)=n*n, dim(b)=n)
979 return value: status flag with: 0 -> valid solution
980 1 -> system singular
981
982 ---------------------------------------------------------------
983
984 cminv
985
986 Invert a general complex matrix in place A -> Inv(A).
987
988 int cminv(Cpx *a,int n)
989 a = pointer to input array of complex n by n matrix A
990 The computation replaces A by its inverse.
991 n = dimension of system (dim(a)=n*n)
992 return value: status flag with: 0 -> valid solution
993 1 -> system singular
994
995 ------------------------------------------------------------------------------
996
997 Hermitian Eigensystems:
998 ------------------------------------------------------------------------------
999
1000 heigval
1001
1002 Compute the eigenvalues of a Hermitian matrix.
1003
1004 void heigval(Cpx *a,double *ev,int n)
1005 a = pointer to array for the Hermitian matrix H
1006 These values are altered by the computation.
1007 ev = pointer to array that is loaded with the
1008 eigenvalues of H by the computation
1009 n = dimension (dim(a)=n*n, dim(ev)=n)
1010
1011 --------------------------------------------------------
1012
1013 heigvec
1014
1015 Compute the eigenvalues and eigenvectors of a Hermitian
1016 matrix.
1017
1018 void heigvec(Cpx *a,double *ev,int n)
1019 a = pointer to array for the hermitian matrix H
1020 This array is loaded with a unitary matrix of
1021 eigenvectors E by the computation.
1022 ev = pointer to array that is loaded with the
1023 eigenvalues of H by the computation
1024 n = dimension (dim(a)=n*n, dim(ev)=n)
1025
1026 The eigen vector matrix output E satisfies
1027
1028 E^*E = I and A = E*D*E^
1029
1030 where D[i,j] = ev[i] for i=j and 0 otherwise
1031 and E^ is the Hermitian conjugate of E.
1032 The columns of E are the eigenvectors of A.
1033
1034 ----------------------------------------------------------
1035
1036 hevmax
1037
1038 Compute the eigenvalue of maximum absolute value and
1039 the corresponding eigenvector of a Hermitian matrix.
1040
1041 double hevmax(Cpx *a,Cpx *u,int n)
1042 Cpx *a,*u; int n;
1043 a = pointer to array for the Hermitian matrix H
1044 u = pointer to array for the eigenvector umax
1045 n = dimension (dim(a)=n*n, dim(u)=n)
1046 return value: emax = eigenvalue of H with largest
1047 absolute value
1048
1049 The eigenvector u and eigenvalue emax are related by u^*A*u = emax.
1050
1051 ------------------------------------------------------------------------------
1052 Hermitian Eigensystem Auxiliaries:
1053 ------------------------------------------------------------------------------
1054
1055 The following routines are called by the Hermitian eigensystem
1056 functions. They are not normally called by the user.
1057
1058 chouse
1059
1060 Transform a Hermitian matrix H to real symmetric tridiagonal
1061 form.
1062
1063 void chouse(Cpx *a,double *d,double *dp,int n)
1064 a = pointer to input array of complex matrix elements of H
1065 This array is altered by the computation
1066 d = pointer to output array of real diagonal elements
1067 dp = pointer to output array of real superdiagonal elements
1068 n = system dimension, with:
1069 dim(a) = n * n, dim(d) = dim(dn) = n;
1070
1071 -----------------------------------------------------------------
1072
1073 chousv
1074
1075 Transform a Hermitian matrix H to real symmetric tridiagonal
1076 form, and compute the unitary matrix of this transformation.
1077
1078 void chousv(Cpx *a,double *d,double *dp,int n)
1079 a = pointer to input array of complex matrix elements of H
1080 The computation replaces this with the unitary matrix
1081 U of the transformation.
1082 d = pointer to output array of real diagonal elements
1083 dp = pointer to output array of real superdiagonal elements
1084 n = system dimension, with:
1085 dim(a) = n*n, dim(d) = dim(dn) = n;
1086
1087 The matrix U satisfies
1088
1089 A = U^*T*U where T is real and tridiagonal,
1090 with T[i,i+1] = T[i+1,i] = dp[i] and T[i,i] = d[i].
1091
1092 ------------------------------------------------------------
1093
1094 qrecvc
1095
1096 Use QR transformations to reduce a real symmetric tridiagonal
1097 matrix to diagonal form, and update a unitary transformation
1098 matrix.
1099
1100 void qrecvc(double *ev,Cpx *evec,double *dp,int n)
1101 ev = pointer to input array of diagonal elements
1102 The computation transforms these to eigenvalues
1103 of the input matrix.
1104 evec = pointer to input array of a unitary transformation
1105 matrix U. The computation applies the QR rotations
1106 to this matrix.
1107 dp = pointer to input array of elements neighboring the
1108 diagonal. These values are altered by the computation.
1109 n = dimension parameter (dim(ev)=dim(dp)=n, dim(evec)=n*n)
1110
1111 This function operates on the output of 'chousv'.
1112
1113 -------------------------------------------------------------------------------
1114
1115 Complex Matrix Utilities:
1116 -------------------------------------------------------------------------------
1117
1118 cvmul
1119
1120 Transform a complex vector u = A*v.
1121
1122 void cvmul(Cpx *u,Cpx *a,Cpx *v,int n)
1123 u = pointer to array of output vector u.
1124 a = pointer to array of transform matrix A.
1125 v = pointer to array of input vector v.
1126 n = dimension (dim(u)=dim(v)=n, dim(a)=n*n)
1127
1128 -----------------------------------------------------------
1129
1130 cvnrm
1131
1132 Compute a Hermitian inner product s = u^*v.
1133
1134 Cpx cvnrm(Cpx *u,Cpx *v,int n)
1135 u = pointer to array of first vector u
1136 v = pointer to array of second vector v
1137 n = dimension (dim(u)=dim(v)=n)
1138 return value: s = complex value of inner product
1139
1140 -----------------------------------------------------------
1141
1142 cmmul
1143
1144 Multiply two square complex matrices C = A * B.
1145
1146 void cmmul(Cpx *c,Cpx *a,Cpx *b,int n)
1147 a = pointer to input array of left matrix factor A
1148 b = pointer to input array of right matrix factor B
1149 c = pointer to array of output product matrix C
1150 n = dimension parameter (dim(c)=dim(a)=dim(b)=n*n)
1151
1152 -------------------------------------------------------------
1153
1154 cmmult
1155
1156 Multiply two complex matrices C = A * B.
1157
1158 void cmmult(Cpx *c,Cpx *a,Cpx *b,int n,int m,int l)
1159 a = pointer to input array of right n by m factor matrix A
1160 b = pointer to input array of left m by l factor matrix B
1161 c = pointer to store for n by l output matrix C
1162 n,m,l = system dimension parameters, with
1163 (dim(c)=n*l, dim(a)=n*m, dim(b)=m*l)
1164
1165 ----------------------------------------------------------------
1166
1167 hconj
1168
1169 Compute the Hermitian conjugate in place, A -> A^.
1170
1171 void hconj(Cpx *a,int n)
1172 a = pointer to input array for the complex matrix A
1173 This is converted to the Hermitian conjugate A^.
1174 n = dimension (dim(a)=n*n)
1175
1176 ----------------------------------------------------------
1177
1178 utrncm
1179
1180 Perform a unitary similarity transformation C = T*B*T^.
1181
1182 void utrncm(Cpx *cm,Cpx *a,Cpx *b,int n)
1183 a = pointer to the array of the transform matrix T
1184 b = pointer to the array of the input matrix B
1185 cm = pointer to output array of the transformed matrix C
1186 n = dimension (dim(cm)=dim(a)=dim(b)=n*n)
1187
1188 ---------------------------------------------------------------
1189
1190 utrnhm
1191
1192 Perform a unitary similarity transformation on a Hermitian
1193 matrix H' = T*H*T^.
1194
1195 void utrnhm(Cpx *hm,Cpx *a,Cpx *b,int n)
1196 a = pointer to the array of the transform matrix T
1197 b = pointer to the array of the Hermitian input matrix H
1198 hm = pointer to array containing Hermitian output matrix H'
1199 n = dimension (dim(cm)=dim(a)=dim(b)=n*n)
1200
1201 -----------------------------------------------------------------
1202
1203 trncm
1204
1205 Transpose a complex square matrix in place A -> A~.
1206
1207 void trncm(Cpx *a,int n)
1208 a = pointer to array of n by n complex matrix A
1209 The computation replaces A by its transpose
1210 n = dimension (dim(a)=n*n)
1211
1212 ---------------------------------------------------------
1213
1214 cmattr
1215
1216 Compute the transpose A = B~ of a complex m by n matrix.
1217
1218 void cmattr(Cpx *a,Cpx *b,int m,int n)
1219 a = pointer to output array of matrix A
1220 b = pointer to input array of matrix B
1221 m, n = matrix dimensions, with B m by n and A n by m
1222 (dim(a)=dim(b)= m*n)
1223
1224 -----------------------------------------------------------------
1225
1226 hmgen
1227
1228 Generate a Hermitian matrix with specified eigen values and
1229 eigenvectors.
1230
1231 void hmgen(Cpx *h,double *ev,Cpx *u,int n)
1232 h = pointer to complex array of output matrix H
1233 ev = pointer to real array of input eigen values
1234 u = pointer to complex array of unitary matrix U
1235 n = dimension (dim(h)=dim(u)=n*n, dim(ev)=n)
1236
1237 If D is a diagonal matrix with D[i,j] = ev[i] for i=j and 0
1238 otherwise. H = U*D*U^. The columns of U are eigenvectors.
1239
1240 -----------------------------------------------------------------
1241
1242 unitary
1243
1244 Generate a random unitary transformation U.
1245
1246 void unitary(Cpx *u,int n)
1247 u = pointer to complex output array for U
1248 n = dimension (dim(u)=n*n)
1249
1250
1251 This function calls on the uniform random generator 'unfl' to
1252 produce random rotation angles. Therefore this random generator
1253 should be initialized by a call of 'setunfl' before calling
1254 'unitary' (see Chapter 7).
1255
1256 ---------------------------------------------------------------------
1257
1258 cmcpy
1259
1260 Copy a complex array A = B.
1261
1262 void cmcpy(Cpx *a,Cpx *b,int n)
1263 a = pointer to store for output array
1264 b = pointer to store for input array
1265 n = dimension of complex arrays A and B
1266
1267 -----------------------------------------------------------
1268
1269 cmprt
1270
1271 Print rows of a complex matrix in a specified format.
1272
1273 void cmprt(Cpx *a,int m,int n,char *f)
1274 a = pointer to array of complex m by n matrix
1275 m = number of columns
1276 n = number of rows
1277 f = character array holding format for complex number
1278 output (ie., "%f, %f ")
1279
1280 Long rows may overflow the print line.