|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/corelib/matrix.c |
source navigation diff markup identifier search freetext search file search |
1 /* $Id: matrix.c,v 6.1 1999/04/02 20:43:30 vakatov Exp $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information (NCBI)
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government do not place any restriction on its use or reproduction.
13 * We would, however, appreciate having the NCBI and the author cited in
14 * any work or product based on this material
15 *
16 * Although all reasonable efforts have been taken to ensure the accuracy
17 * and reliability of the software and data, the NLM and the U.S.
18 * Government do not and cannot warrant the performance or results that
19 * may be obtained by using this software or data. The NLM and the U.S.
20 * Government disclaim all warranties, express or implied, including
21 * warranties of performance, merchantability or fitness for any particular
22 * purpose.
23 *
24 * ===========================================================================
25 *
26 * Author: Denis Vakatov
27 *
28 * File Description:
29 * Basic matrix & vector handling library.
30 * NOTE: most of advanced functions are valid for square matrices only!
31 *
32 * ===========================================================================
33 * $Log: matrix.c,v $
34 * Revision 6.1 1999/04/02 20:43:30 vakatov
35 * DLL'd for MS-Win
36 * Added detailed API function descriptions
37 *
38 * ==========================================================================
39 */
40
41 #include <matrix.h>
42 #include <ncbimem.h>
43 #include <ncbierr.h>
44
45
46 typedef struct Nlm_MatrixTag {
47 Nlm_Uint4 n_row;
48 Nlm_Uint4 n_column;
49 Nlm_FloatHi m[1];
50 } Nlm_MatrixStruct;
51
52
53 #ifdef CHECK_RANGE_MATRIX
54 static Nlm_FloatHiPtr VALPtr(Nlm_Matrix mat, Nlm_Uint4 row, Nlm_Uint4 column)
55 {
56 ASSERT ( row < mat->n_row && column < mat->n_column );
57 return &mat->m[row * mat->n_column + column];
58 }
59 #define VAL(mat,row,column) (*VALPtr(mat,row,column))
60 #else /* CHECK_RANGE_MATRIX */
61 #define VAL(matrix, row, column) (matrix->m[row * matrix->n_column + column])
62 #endif /* CHECK_RANGE_MATRIX */
63
64
65
66 #define MAT_SIZE(mat) (sizeof(Nlm_MatrixStruct) + (mat->n_row * mat->n_column - 1) * sizeof(Nlm_FloatHi))
67
68
69 /***********************************************************************
70 * INTERNAL
71 ***********************************************************************/
72
73
74 static Nlm_Boolean lu_decompose
75 (Nlm_Matrix mat,
76 Nlm_Uint4Ptr indx)
77 {
78 Nlm_Uint4 i, j, k, imax = UINT4_MAX;
79 Nlm_FloatHi max, temp, sum;
80
81 Nlm_Uint4 n = mat->n_row;
82 Nlm_FloatHiPtr row_scale = (Nlm_FloatHiPtr)
83 Nlm_MemNew(sizeof(Nlm_FloatHi) * n);
84
85 ASSERT ( mat->n_row == mat->n_column );
86
87 for (i = 0; i < n; i++)
88 {
89 max = 0.0;
90 for (j = 0; j < n; j++)
91 if ((temp = fabs( VAL(mat,i,j) )) > max)
92 max = temp;
93
94 if (max == 0.0) {
95 Nlm_MemFree( row_scale );
96 return FALSE;
97 }
98
99 row_scale[i] = 1.0 / max;
100 indx[i] = i;
101 }
102
103 for (j = 0; j < n; j++)
104 {
105 for (i = 0; i < j; i++)
106 {
107 sum = VAL(mat,i,j);
108 for (k = 0; k < i; k++)
109 sum -= VAL(mat,i,k) * VAL(mat,k,j);
110 VAL(mat,i,j) = sum;
111 }
112
113 max = 0.0;
114 for (i = j; i < n; i++)
115 {
116 sum = VAL(mat,i,j);
117 for (k = 0; k < j; k++)
118 sum -= VAL(mat,i,k) * VAL(mat,k,j);
119 VAL(mat,i,j) = sum;
120
121 if ((temp = row_scale[i] * fabs(sum)) >= max) {
122 max = temp;
123 imax = i;
124 }
125 }
126
127 if (j != imax)
128 { /* row interchange */
129 for (k = 0; k < n; k++)
130 {
131 temp = VAL(mat,imax,k);
132 VAL(mat,imax,k) = VAL(mat,j,k);
133 VAL(mat,j,k) = temp;
134 }
135
136 row_scale[imax] = row_scale[j];
137
138 k = indx[j];
139 indx[j] = indx[imax];
140 indx[imax] = k;
141 }
142
143 if ((j+1) != n)
144 {
145 temp = 1.0 / VAL(mat,j,j);
146 for (i = j + 1; i < n; i++)
147 VAL(mat,i,j) *= temp;
148 }
149 }
150
151 Nlm_MemFree( row_scale );
152 return TRUE;
153 }
154
155
156 static Nlm_Matrix lu_back_subst
157 (const Nlm_Matrix mat,
158 Uint4Ptr indx,
159 const Nlm_Matrix vector)
160 {
161 Uint4 i,j;
162 Uint4 n = mat->n_row;
163 Uint4 i_nonzero = n; /* it means -- only zero nodes up to now */
164
165 Nlm_Matrix res_vector = Nlm_MatrixNew(vector->n_row, 1);
166 for (i = 0; i < res_vector->n_row; i++)
167 VAL(res_vector, i, 0) = VAL(vector, indx[i], 0);
168
169 ASSERT ( mat->n_row == mat->n_column );
170 ASSERT ( mat->n_row == res_vector->n_row );
171
172 for (i = 0; i < n; i++)
173 {
174 FloatHi sum = VAL(res_vector, i,0);
175
176 if (i_nonzero != n)
177 for (j = i_nonzero; j < i; j++)
178 sum -= VAL(mat, i,j) * VAL(res_vector, j,0);
179 else if ( sum )
180 i_nonzero = i;
181
182 VAL(res_vector, i,0) = sum;
183 }
184
185 for (i = n; i-- > 0; )
186 {
187 FloatHi sum = VAL(res_vector, i,0);
188 for (j = i+1; j < n; j++)
189 sum -= VAL(mat, i,j) * VAL(res_vector, j,0);
190 VAL(res_vector, i,0) = sum / VAL(mat, i,i);
191 }
192
193 return res_vector;
194 }
195
196
197
198 /***********************************************************************
199 * EXTERNAL
200 ***********************************************************************/
201
202
203 NLM_EXTERN Nlm_Matrix Nlm_MatrixNew
204 (Nlm_Uint4 n_row,
205 Nlm_Uint4 n_column)
206 {
207 Nlm_Matrix mat = (Nlm_Matrix)
208 Nlm_MemNew(sizeof(Nlm_MatrixStruct) +
209 (n_row * n_column - 1) * sizeof(Nlm_FloatHi));
210 ASSERT ( n_row && n_column );
211
212 mat->n_row = n_row;
213 mat->n_column = n_column;
214 return mat;
215 }
216
217
218 NLM_EXTERN void Nlm_MatrixDelete
219 (Nlm_Matrix mat)
220 {
221 Nlm_MemFree( mat );
222 }
223
224
225 NLM_EXTERN void Nlm_MatrixSetNode
226 (Nlm_Matrix mat,
227 Nlm_Uint4 row,
228 Nlm_Uint4 column,
229 Nlm_FloatHi value)
230 {
231 VAL(mat, row, column) = value;
232 }
233
234
235 NLM_EXTERN void Nlm_MatrixSetRow
236 (Nlm_Matrix mat,
237 Nlm_Uint4 row,
238 const Nlm_Matrix mat_src,
239 Nlm_Uint4 row_src)
240 {
241 Uint4 j;
242 ASSERT ( mat->n_column == mat_src->n_column );
243
244 for (j = 0; j < mat->n_column; j++)
245 VAL(mat, row, j) = VAL(mat_src, row_src, j);
246 }
247
248
249 NLM_EXTERN void Nlm_MatrixSetColumn
250 (Nlm_Matrix mat,
251 Nlm_Uint4 column,
252 const Nlm_Matrix mat_src,
253 Nlm_Uint4 column_src)
254 {
255 Uint4 i;
256 ASSERT ( mat->n_row == mat_src->n_row );
257
258 for (i = 0; i < mat->n_row; i++)
259 VAL(mat, i, column) = VAL(mat_src, i, column_src);
260 }
261
262
263 NLM_EXTERN Nlm_FloatHi Nlm_MatrixNode
264 (const Nlm_Matrix mat,
265 Nlm_Uint4 row,
266 Nlm_Uint4 column)
267 {
268 return VAL(mat, row, column);
269 }
270
271
272 NLM_EXTERN Nlm_Matrix Nlm_MatrixRow
273 (const Nlm_Matrix mat,
274 Nlm_Uint4 row)
275 {
276 Uint4 j;
277 Nlm_Matrix row_mat = Nlm_MatrixNew(1, mat->n_column);
278
279 for (j = 0; j < mat->n_column; j++)
280 VAL(row_mat, 0, j) = VAL(mat, row, j);
281
282 return row_mat;
283 }
284
285
286 NLM_EXTERN Nlm_Matrix Nlm_MatrixColumn
287 (const Nlm_Matrix mat,
288 Nlm_Uint4 column)
289 {
290 Uint4 i;
291 Nlm_Matrix column_mat = Nlm_MatrixNew(mat->n_row, 1);
292
293 for (i = 0; i < mat->n_row; i++)
294 VAL(column_mat, i, 0) = VAL(mat, i, column);
295
296 return column_mat;
297 }
298
299
300 NLM_EXTERN Nlm_Boolean Nlm_MatrixCompare
301 (const Nlm_Matrix mat1,
302 const Nlm_Matrix mat2)
303 {
304 ASSERT ( mat1->n_row == mat1->n_row );
305 ASSERT ( mat1->n_column == mat1->n_column );
306 return (Nlm_Boolean)
307 (Nlm_MemCmp((VoidPtr)mat1, (VoidPtr)mat2, MAT_SIZE(mat1)) == 0);
308 }
309
310
311 NLM_EXTERN Nlm_Matrix Nlm_MatrixCopy
312 (const Nlm_Matrix mat)
313 {
314 size_t mat_size = MAT_SIZE( mat );
315 Nlm_Matrix c_mat = (Nlm_Matrix)Nlm_MemNew( mat_size );
316
317 Nlm_MemCpy((VoidPtr)c_mat, (VoidPtr)mat, mat_size);
318 return c_mat;
319 }
320
321
322 NLM_EXTERN Nlm_Matrix Nlm_MatrixTranspose
323 (const Nlm_Matrix mat)
324 {
325 Uint4 i,j;
326 Nlm_Matrix t_mat = Nlm_MatrixNew(mat->n_column, mat->n_row);
327
328 for (i = 0; i < mat->n_row; i++)
329 for (j = 0; j < mat->n_column; j++)
330 VAL(t_mat, i, j) = VAL(mat, j, i);
331
332 return t_mat;
333 }
334
335
336 NLM_EXTERN Nlm_Matrix Nlm_MatrixMultiply
337 (const Nlm_Matrix mat_left,
338 const Nlm_Matrix mat_right)
339 {
340 Uint4 n_row = mat_left->n_row;
341 Uint4 n_column = mat_right->n_column;
342 Nlm_Matrix mat = Nlm_MatrixNew(n_row, n_column);
343
344 ASSERT ( mat_left->n_column == mat_right->n_row );
345
346 {{
347 Uint4 n_sum = mat_left->n_column;
348 Uint4 i,j,k;
349 for (i = 0; i < n_row; i++)
350 for (j = 0; j < n_column; j++)
351 for (k = 0; k < n_sum; k++)
352 VAL(mat, i, j) += VAL(mat_left, i, k) * VAL(mat_right, k, j);
353 }}
354
355 return mat;
356 }
357
358
359 NLM_EXTERN Nlm_Matrix Nlm_MatrixSolve
360 (const Nlm_Matrix mat,
361 const Nlm_Matrix vector)
362 {
363 Nlm_Matrix d_mat = Nlm_MatrixCopy( mat );
364 Nlm_Uint4Ptr indx = (Uint4Ptr)Nlm_MemNew(sizeof(Nlm_Uint4) * mat->n_row);
365
366 ASSERT ( mat->n_row == mat->n_column );
367 ASSERT ( vector->n_row == mat->n_column );
368 ASSERT ( vector->n_column == 1 );
369
370 VERIFY ( lu_decompose(d_mat, indx) );
371
372 {{
373 Nlm_Matrix res_vector = lu_back_subst(d_mat, indx, vector);
374 Nlm_MemFree( indx );
375 Nlm_MatrixDelete( d_mat );
376 return res_vector;
377 }}
378 }
379
380
381 NLM_EXTERN Nlm_Matrix Nlm_MatrixInvert
382 (const Nlm_Matrix mat)
383 {
384 Nlm_Matrix res_matrix = Nlm_MatrixNew(mat->n_row, mat->n_column);
385 Nlm_Matrix unit_vector = Nlm_MatrixNew(mat->n_row, 1);
386
387 Uint4 j;
388 for (j = 0; j < mat->n_column; j++) {
389 VAL(unit_vector, j, 0) = 1.0;
390 {{
391 Nlm_Matrix res_vector = Nlm_MatrixSolve(mat, unit_vector);
392 Nlm_MatrixSetColumn(res_matrix, j, res_vector, 0);
393 Nlm_MatrixDelete( res_vector );
394 }}
395 VAL(unit_vector, j, 0) = 0;
396 }
397
398 Nlm_MatrixDelete( unit_vector );
399 return res_matrix;
400 }
401
402
403 NLM_EXTERN void Nlm_MatrixPrint
404 (const Nlm_Matrix mat,
405 FILE* fd,
406 const Char* descr)
407 {
408 Uint4 i,j;
409
410 if ( descr )
411 fprintf(fd, "\n%s:\n", descr);
412
413 for (i = 0; i < mat->n_row; i++) {
414 for (j = 0; j < mat->n_column; j++)
415 fprintf(fd, "%13g ", VAL(mat, i, j));
416 fprintf(fd, "\n");
417 }
418 }
419
420
421 /***********************************************************************
422 * TEST
423 ***********************************************************************/
424
425 #ifdef TEST_MODULE_MATRIX
426
427 #include <ncbifile.h>
428
429 static void TestMatrix(Nlm_FloatHiPtr float_mat, Nlm_Uint4 dim, FILE *fd)
430 {
431 Nlm_Matrix mat = Nlm_MatrixNew(dim, dim);
432 Nlm_Matrix inv_mat, unit_mat, inv2_mat;
433
434 Nlm_Uint4 i,j;
435 for (i = 0; i < dim; i++)
436 for (j = 0; j < dim; j++)
437 Nlm_MatrixSetNode(mat, i, j, float_mat[i*dim + j]);
438 Nlm_MatrixPrint(mat, fd, "Original Matrix:");
439
440 inv_mat = Nlm_MatrixInvert( mat );
441 Nlm_MatrixPrint(inv_mat, fd, "Inverted Matrix:");
442
443 unit_mat = Nlm_MatrixMultiply(mat, inv_mat);
444 Nlm_MatrixPrint(unit_mat, fd, "Must be [1]:");
445
446 inv2_mat = Nlm_MatrixInvert( inv_mat );
447 Nlm_MatrixPrint(inv2_mat, fd, "Inverted Twice Matrix:");
448
449 Nlm_MatrixDelete( inv2_mat );
450 Nlm_MatrixDelete( unit_mat );
451 Nlm_MatrixDelete( inv_mat );
452 Nlm_MatrixDelete( mat );
453 }
454
455
456
457 static Nlm_FloatHi mat1[1][1] = {
458 { 1 }
459 };
460
461 static Nlm_FloatHi mat2[2][2] = {
462 { 3, 2 },
463 { 4, 1 },
464 };
465
466 static Nlm_FloatHi mat3[3][3] = {
467 { 1, 2, 3 },
468 { 4, 5, 6 },
469 { 0, 8, 7 }
470 };
471
472 static Nlm_FloatHi mat4[4][4] = {
473 { 0, 9, 4, 0 },
474 { 1, 5, 6, 4 },
475 { 9, 5, 2, 0 },
476 { 0, 0, 7, 1 }
477 };
478
479 #define N_MAT 4
480 static Nlm_FloatHiPtr test_mat[N_MAT] = {
481 (Nlm_FloatHiPtr)mat1,
482 (Nlm_FloatHiPtr)mat2,
483 (Nlm_FloatHiPtr)mat3,
484 (Nlm_FloatHiPtr)mat4
485 };
486
487
488 Nlm_Int2 Nlm_Main( void )
489 {
490 Nlm_Uint4 dim;
491 FILE *fd = Nlm_FileOpen("matrix.log", "w");
492 ASSERT ( fd );
493
494 for (dim = 1; dim <= N_MAT; dim++)
495 TestMatrix(test_mat[dim-1], dim, fd);
496
497 Nlm_FileClose( fd );
498 return 0;
499 }
500
501 #endif /* TEST_MODULE_MATRIX */
502 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |