| 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. |