1 // =============================================================================
2 // === qrtest ==================================================================
3 // =============================================================================
4
5 // This is an exhaustive test for SuiteSparseQR. With the right input matrices,
6 // it tests each and every line of code in the package. A malloc wrapper is
7 // used that can pretend to run out of memory, to test the out-of-memory
8 // conditions in the package.
9 //
10 // To compile and run this test, type "make". To compile and run with valgrind,
11 // type "make vgo".
12 //
13 // For best results, this test requires a vanilla BLAS and LAPACK library (see
14 // the FLIB definition in the Makefile). The vanilla BLAS should be the
15 // standard reference BLAS, and both it and LAPACK should be compiled with -g
16 // for best results. With some highly-optimized BLAS packages, valgrind
17 // complains about not understanding some of the assembly-level instructions
18 // used.
19
20 #include "spqr.hpp"
21 #include "SuiteSparseQR_C.h"
22
23 // Use a global variable, to compute Inf. This could be done with
24 // #define INF (1./0.), but the overzealous g++ compiler complains
25 // about divide-by-zero.
26 double xx = 1 ;
27 double yy = 0 ;
28 #define INF (xx / yy)
29 #define CHECK_NAN(x) (((x) < 0) || ((x) != (x)) ? INF : (x))
30
31 #define NTOL 4
32
33 // =============================================================================
34 // === qrtest_C ================================================================
35 // =============================================================================
36
37 extern "C" {
38 void qrtest_C
39 (
40 cholmod_sparse *A,
41 double anorm,
42 double errs [5],
43 double maxresid [2][2],
44 cholmod_common *cc
45 ) ;
46 }
47
48 // =============================================================================
49 // === memory testing ==========================================================
50 // =============================================================================
51
52 Long my_tries = -2 ; // number of mallocs to allow (-2 means allow all)
53 Long my_punt = FALSE ; // if true, then my_malloc will fail just once
54
set_tries(Long tries)55 void set_tries (Long tries)
56 {
57 my_tries = tries ;
58 }
59
set_punt(Long punt)60 void set_punt (Long punt)
61 {
62 my_punt = punt ;
63 }
64
my_malloc(size_t size)65 void *my_malloc (size_t size)
66 {
67 if (my_tries >= 0 || (my_punt && my_tries >= -1)) my_tries-- ;
68 if (my_tries == -1)
69 {
70 // printf ("malloc pretends to fail\n") ;
71 return (NULL) ; // pretend to fail
72 }
73 return (malloc (size)) ;
74 }
75
my_calloc(size_t n,size_t size)76 void *my_calloc (size_t n, size_t size)
77 {
78 if (my_tries >= 0 || (my_punt && my_tries >= -1)) my_tries-- ;
79 if (my_tries == -1)
80 {
81 // printf ("calloc pretends to fail\n") ;
82 return (NULL) ; // pretend to fail
83 }
84 return (calloc (n, size)) ;
85 }
86
my_realloc(void * p,size_t size)87 void *my_realloc (void *p, size_t size)
88 {
89 if (my_tries >= 0 || (my_punt && my_tries >= -1)) my_tries-- ;
90 if (my_tries == -1)
91 {
92 // printf ("realloc pretends to fail\n") ;
93 return (NULL) ; // pretend to fail
94 }
95 return (realloc (p, size)) ;
96 }
97
my_free(void * p)98 void my_free (void *p)
99 {
100 if (p) free (p) ;
101 }
102
my_handler(int status,const char * file,int line,const char * msg)103 void my_handler (int status, const char *file, int line, const char *msg)
104 {
105 printf ("ERROR: %d in %s line %d : %s\n", status, file, line, msg) ;
106 }
107
normal_memory_handler(cholmod_common * cc)108 void normal_memory_handler (cholmod_common *cc)
109 {
110 SuiteSparse_config.printf_func = printf ;
111 SuiteSparse_config.malloc_func = malloc ;
112 SuiteSparse_config.calloc_func = calloc ;
113 SuiteSparse_config.realloc_func = realloc ;
114 SuiteSparse_config.free_func = free ;
115
116 cc->error_handler = my_handler ;
117 cholmod_l_free_work (cc) ;
118 my_tries = -2 ;
119 my_punt = FALSE ;
120 }
121
test_memory_handler(cholmod_common * cc)122 void test_memory_handler (cholmod_common *cc)
123 {
124 SuiteSparse_config.printf_func = NULL ;
125 SuiteSparse_config.malloc_func = my_malloc ;
126 SuiteSparse_config.calloc_func = my_calloc ;
127 SuiteSparse_config.realloc_func = my_realloc ;
128 SuiteSparse_config.free_func = my_free ;
129
130 cc->error_handler = NULL ;
131 cholmod_l_free_work (cc) ;
132 my_tries = -2 ;
133 my_punt = FALSE ;
134 }
135
136
137 // =============================================================================
138 // === SPQR_qmult ==============================================================
139 // =============================================================================
140
141 // wrapper for SuiteSparseQR_qmult (dense), optionally testing memory alloc.
142
SPQR_qmult(Long method,cholmod_sparse * H,cholmod_dense * Tau,Long * HPinv,cholmod_dense * X,cholmod_common * cc,Long memory_test,Long memory_punt)143 template <typename Entry> cholmod_dense *SPQR_qmult
144 (
145 // arguments for SuiteSparseQR_qmult:
146 Long method,
147 cholmod_sparse *H,
148 cholmod_dense *Tau,
149 Long *HPinv,
150 cholmod_dense *X,
151 cholmod_common *cc,
152
153 // malloc control
154 Long memory_test, // if TRUE, test malloc error handling
155 Long memory_punt // if TRUE, test punt case
156 )
157 {
158 cholmod_dense *Y = NULL ;
159 if (!memory_test)
160 {
161 // just call the method directly; no memory testing
162 Y = SuiteSparseQR_qmult <Entry> (method, H, Tau, HPinv, X, cc) ;
163 }
164 else
165 {
166 // test malloc error handling
167 Long tries ;
168 test_memory_handler (cc) ;
169 my_punt = memory_punt ;
170 for (tries = 0 ; my_tries < 0 ; tries++)
171 {
172 my_tries = tries ;
173 Y = SuiteSparseQR_qmult <Entry> (method, H, Tau, HPinv, X, cc) ;
174 if (cc->status == CHOLMOD_OK) break ;
175 }
176 normal_memory_handler (cc) ;
177 }
178 return (Y) ;
179 }
180
181
182 // =============================================================================
183 // === SPQR_qmult_sparse =======================================================
184 // =============================================================================
185
186 // wrapper for SuiteSparseQR_qmult (sparse), optionally testing memory alloc.
187
SPQR_qmult(Long method,cholmod_sparse * H,cholmod_dense * Tau,Long * HPinv,cholmod_sparse * X,cholmod_common * cc,Long memory_test,Long memory_punt)188 template <typename Entry> cholmod_sparse *SPQR_qmult
189 (
190 // arguments for SuiteSparseQR_qmult:
191 Long method,
192 cholmod_sparse *H,
193 cholmod_dense *Tau,
194 Long *HPinv,
195 cholmod_sparse *X,
196 cholmod_common *cc,
197
198 // malloc control
199 Long memory_test, // if TRUE, test malloc error handling
200 Long memory_punt // if TRUE, test punt case
201 )
202 {
203 cholmod_sparse *Y = NULL ;
204 if (!memory_test)
205 {
206 // just call the method directly; no memory testing
207 Y = SuiteSparseQR_qmult <Entry> (method, H, Tau, HPinv, X, cc) ;
208 }
209 else
210 {
211 // test malloc error handling
212 Long tries ;
213 test_memory_handler (cc) ;
214 my_punt = memory_punt ;
215 for (tries = 0 ; my_tries < 0 ; tries++)
216 {
217 my_tries = tries ;
218 Y = SuiteSparseQR_qmult <Entry> (method, H, Tau, HPinv, X, cc);
219 if (cc->status == CHOLMOD_OK) break ;
220 }
221 normal_memory_handler (cc) ;
222 }
223 return (Y) ;
224 }
225
226 #ifndef NEXPERT
227
228 // =============================================================================
229 // === SPQR_qmult (dense case) =================================================
230 // =============================================================================
231
232 // wrapper for SuiteSparseQR_qmult (dense), optionally testing memory alloc.
233
SPQR_qmult(Long method,SuiteSparseQR_factorization<Entry> * QR,cholmod_dense * X,cholmod_common * cc,Long memory_test,Long memory_punt)234 template <typename Entry> cholmod_dense *SPQR_qmult
235 (
236 // arguments for SuiteSparseQR_qmult:
237 Long method,
238 SuiteSparseQR_factorization <Entry> *QR,
239 cholmod_dense *X,
240 cholmod_common *cc,
241
242 // malloc control
243 Long memory_test, // if TRUE, test malloc error handling
244 Long memory_punt // if TRUE, test punt case
245 )
246 {
247 cholmod_dense *Y = NULL ;
248 if (!memory_test)
249 {
250 // just call the method directly; no memory testing
251 Y = SuiteSparseQR_qmult <Entry> (method, QR, X, cc) ;
252 }
253 else
254 {
255 // test malloc error handling
256 Long tries ;
257 test_memory_handler (cc) ;
258 my_punt = memory_punt ;
259 for (tries = 0 ; my_tries < 0 ; tries++)
260 {
261 my_tries = tries ;
262 Y = SuiteSparseQR_qmult <Entry> (method, QR, X, cc) ;
263 if (cc->status == CHOLMOD_OK) break ;
264 }
265 normal_memory_handler (cc) ;
266 }
267 return (Y) ;
268 }
269
270 // =============================================================================
271 // === SPQR_qmult (sparse case) ================================================
272 // =============================================================================
273
274 // wrapper for SuiteSparseQR_qmult (sparse), optionally testing memory alloc.
275
SPQR_qmult(Long method,SuiteSparseQR_factorization<Entry> * QR,cholmod_sparse * X,cholmod_common * cc,Long memory_test,Long memory_punt)276 template <typename Entry> cholmod_sparse *SPQR_qmult
277 (
278 // arguments for SuiteSparseQR_qmult:
279 Long method,
280 SuiteSparseQR_factorization <Entry> *QR,
281 cholmod_sparse *X,
282 cholmod_common *cc,
283
284 // malloc control
285 Long memory_test, // if TRUE, test malloc error handling
286 Long memory_punt // if TRUE, test punt case
287 )
288 {
289 cholmod_sparse *Y = NULL ;
290 if (!memory_test)
291 {
292 // just call the method directly; no memory testing
293 Y = SuiteSparseQR_qmult <Entry> (method, QR, X, cc) ;
294 }
295 else
296 {
297 // test malloc error handling
298 Long tries ;
299 test_memory_handler (cc) ;
300 my_punt = memory_punt ;
301 for (tries = 0 ; my_tries < 0 ; tries++)
302 {
303 my_tries = tries ;
304 Y = SuiteSparseQR_qmult <Entry> (method, QR, X, cc) ;
305 if (cc->status == CHOLMOD_OK) break ;
306 }
307 normal_memory_handler (cc) ;
308 }
309 return (Y) ;
310 }
311
312
313 // =============================================================================
314 // === SPQR_solve (dense case) =================================================
315 // =============================================================================
316
317 // Wrapper for testing SuiteSparseQR_solve
318
SPQR_solve(Long system,SuiteSparseQR_factorization<Entry> * QR,cholmod_dense * B,cholmod_common * cc,Long memory_test,Long memory_punt)319 template <typename Entry> cholmod_dense *SPQR_solve
320 (
321 // arguments for SuiteSparseQR_solve:
322 Long system,
323 SuiteSparseQR_factorization <Entry> *QR,
324 cholmod_dense *B,
325 cholmod_common *cc,
326
327 // malloc control
328 Long memory_test, // if TRUE, test malloc error handling
329 Long memory_punt // if TRUE, test punt case
330 )
331 {
332 cholmod_dense *X = NULL ;
333 if (!memory_test)
334 {
335 // just call the method directly; no memory testing
336 X = SuiteSparseQR_solve (system, QR, B, cc) ;
337 }
338 else
339 {
340 // test malloc error handling
341 Long tries ;
342 test_memory_handler (cc) ;
343 my_punt = memory_punt ;
344 for (tries = 0 ; my_tries < 0 ; tries++)
345 {
346 my_tries = tries ;
347 X = SuiteSparseQR_solve (system, QR, B, cc) ;
348 if (cc->status == CHOLMOD_OK) break ;
349 }
350 normal_memory_handler (cc) ;
351 }
352 return (X) ;
353 }
354
355
356 // =============================================================================
357 // === SPQR_solve (sparse case) ================================================
358 // =============================================================================
359
360 // Wrapper for testing SuiteSparseQR_solve
361
SPQR_solve(Long system,SuiteSparseQR_factorization<Entry> * QR,cholmod_sparse * B,cholmod_common * cc,Long memory_test,Long memory_punt)362 template <typename Entry> cholmod_sparse *SPQR_solve
363 (
364 // arguments for SuiteSparseQR_solve:
365 Long system,
366 SuiteSparseQR_factorization <Entry> *QR,
367 cholmod_sparse *B,
368 cholmod_common *cc,
369
370 // malloc control
371 Long memory_test, // if TRUE, test malloc error handling
372 Long memory_punt // if TRUE, test punt case
373 )
374 {
375 cholmod_sparse *X = NULL ;
376 if (!memory_test)
377 {
378 // just call the method directly; no memory testing
379 X = SuiteSparseQR_solve (system, QR, B, cc) ;
380 }
381 else
382 {
383 // test malloc error handling
384 Long tries ;
385 test_memory_handler (cc) ;
386 my_punt = memory_punt ;
387 for (tries = 0 ; my_tries < 0 ; tries++)
388 {
389 my_tries = tries ;
390 X = SuiteSparseQR_solve (system, QR, B, cc) ;
391 if (cc->status == CHOLMOD_OK) break ;
392 }
393 normal_memory_handler (cc) ;
394 }
395 return (X) ;
396 }
397
398
399 // =============================================================================
400 // === SPQR_min2norm (dense case) ==============================================
401 // =============================================================================
402
403 // Wrapper for testing SuiteSparseQR_min2norm
404
SPQR_min2norm(int ordering,double tol,cholmod_sparse * A,cholmod_dense * B,cholmod_common * cc,Long memory_test,Long memory_punt)405 template <typename Entry> cholmod_dense *SPQR_min2norm
406 (
407 // arguments for SuiteSparseQR_min2norm:
408 int ordering,
409 double tol,
410 cholmod_sparse *A,
411 cholmod_dense *B,
412 cholmod_common *cc,
413
414 // malloc control
415 Long memory_test, // if TRUE, test malloc error handling
416 Long memory_punt // if TRUE, test punt case
417 )
418 {
419 cholmod_dense *X = NULL ;
420 if (!memory_test)
421 {
422 // just call the method directly; no memory testing
423 X = SuiteSparseQR_min2norm <Entry> (ordering, tol, A, B, cc) ;
424 }
425 else
426 {
427 // test malloc error handling
428 Long tries ;
429 test_memory_handler (cc) ;
430 my_punt = memory_punt ;
431 for (tries = 0 ; my_tries < 0 ; tries++)
432 {
433 my_tries = tries ;
434 X = SuiteSparseQR_min2norm <Entry> (ordering, tol, A, B, cc) ;
435 if (cc->status == CHOLMOD_OK) break ;
436 }
437 normal_memory_handler (cc) ;
438 }
439 return (X) ;
440 }
441
442 // =============================================================================
443 // === SPQR_min2norm (sparse case) =============================================
444 // =============================================================================
445
446 // Wrapper for testing SuiteSparseQR_min2norm
447
SPQR_min2norm(int ordering,double tol,cholmod_sparse * A,cholmod_sparse * B,cholmod_common * cc,Long memory_test,Long memory_punt)448 template <typename Entry> cholmod_sparse *SPQR_min2norm
449 (
450 // arguments for SuiteSparseQR_min2norm:
451 int ordering,
452 double tol,
453 cholmod_sparse *A,
454 cholmod_sparse *B,
455 cholmod_common *cc,
456
457 // malloc control
458 Long memory_test, // if TRUE, test malloc error handling
459 Long memory_punt // if TRUE, test punt case
460 )
461 {
462 cholmod_sparse *X = NULL ;
463 if (!memory_test)
464 {
465 // just call the method directly; no memory testing
466 X = SuiteSparseQR_min2norm <Entry> (ordering, tol, A, B, cc) ;
467 }
468 else
469 {
470 // test malloc error handling
471 Long tries ;
472 test_memory_handler (cc) ;
473 my_punt = memory_punt ;
474 for (tries = 0 ; my_tries < 0 ; tries++)
475 {
476 my_tries = tries ;
477 X = SuiteSparseQR_min2norm <Entry> (ordering, tol, A, B, cc) ;
478 if (cc->status == CHOLMOD_OK) break ;
479 }
480 normal_memory_handler (cc) ;
481 }
482 return (X) ;
483 }
484
485 // =============================================================================
486 // === SPQR_factorize ==========================================================
487 // =============================================================================
488
489 // Wrapper for testing SuiteSparseQR_factorize or
490 // SuiteSparseQR_symbolic and SuiteSparseQR_numeric
491
SPQR_factorize(int ordering,double tol,cholmod_sparse * A,cholmod_common * cc,int split,Long memory_test,Long memory_punt)492 template <typename Entry> SuiteSparseQR_factorization <Entry> *SPQR_factorize
493 (
494 // arguments for SuiteSparseQR_factorize:
495 int ordering,
496 double tol,
497 cholmod_sparse *A,
498 cholmod_common *cc,
499
500 // method to use
501 int split, // if 1 use SuiteSparseQR_symbolic followed by
502 // SuiteSparseQR_numeric, if 0 use
503 // SuiteSparseQR_factorize, if 2, do the
504 // numeric factorization twice, just for testing.
505 // if 3 use SuiteSparseQR_C_factorize
506 // if 3 use SuiteSparseQR_C_symbolic / _C_numeric
507
508 // malloc control
509 Long memory_test, // if TRUE, test malloc error handling
510 Long memory_punt // if TRUE, test punt case
511 )
512 {
513 SuiteSparseQR_factorization <Entry> *QR ;
514 SuiteSparseQR_C_factorization *C_QR ;
515 if (!memory_test)
516 {
517 // just call the method directly; no memory testing
518
519 if (split == 4)
520 {
521
522 C_QR = SuiteSparseQR_C_symbolic (ordering, tol >= 0, A, cc) ;
523 SuiteSparseQR_C_numeric (tol, A, C_QR, cc) ;
524 if (C_QR == NULL)
525 {
526 cc->status = CHOLMOD_OUT_OF_MEMORY ;
527 QR = NULL ;
528 }
529 else
530 {
531 QR = (SuiteSparseQR_factorization <Entry> *)
532 (C_QR->factors) ;
533 if (QR == NULL || QR->QRnum == NULL)
534 {
535 cc->status = CHOLMOD_OUT_OF_MEMORY ;
536 QR = NULL ;
537 }
538 else
539 {
540 // QR itself will be kept; free the C wrapper
541 C_QR->factors = NULL ;
542 cc->status = CHOLMOD_OK ;
543 if (QR == NULL) printf ("Hey!\n") ;
544 }
545 }
546 SuiteSparseQR_C_free (&C_QR, cc) ;
547
548 }
549 else if (split == 3)
550 {
551
552 C_QR = SuiteSparseQR_C_factorize (ordering, tol, A, cc) ;
553 int save = cc->status ;
554 if (C_QR == NULL)
555 {
556 QR = NULL ;
557 }
558 else
559 {
560 QR = (SuiteSparseQR_factorization <Entry> *) (C_QR->factors) ;
561 C_QR->factors = NULL ;
562 SuiteSparseQR_C_free (&C_QR, cc) ;
563 }
564 cc->status = save ;
565
566 }
567 else if (split == 2)
568 {
569 QR = SuiteSparseQR_symbolic <Entry> (ordering,
570 tol >= 0 || tol <= SPQR_DEFAULT_TOL, A, cc) ;
571 ASSERT (QR != NULL) ;
572 SuiteSparseQR_numeric <Entry> (tol, A, QR, cc) ;
573 // just for testing
574 SuiteSparseQR_numeric <Entry> (tol, A, QR, cc) ;
575 }
576 else if (split == 1)
577 {
578 // split symbolic/numeric, no singletons exploited
579 QR = SuiteSparseQR_symbolic <Entry> (ordering,
580 tol >= 0 || tol <= SPQR_DEFAULT_TOL, A, cc) ;
581 ASSERT (QR != NULL) ;
582 SuiteSparseQR_numeric <Entry> (tol, A, QR, cc) ;
583 }
584 else
585 {
586 QR = SuiteSparseQR_factorize <Entry> (ordering, tol, A, cc) ;
587 }
588
589 }
590 else
591 {
592 // test malloc error handling
593 Long tries ;
594 test_memory_handler (cc) ;
595 my_punt = memory_punt ;
596 for (tries = 0 ; my_tries < 0 ; tries++)
597 {
598 my_tries = tries ;
599
600 if (split == 4)
601 {
602
603 C_QR = SuiteSparseQR_C_symbolic (ordering, tol >= 0, A, cc) ;
604 SuiteSparseQR_C_numeric (tol, A, C_QR, cc) ;
605 if (C_QR == NULL)
606 {
607 cc->status = CHOLMOD_OUT_OF_MEMORY ;
608 QR = NULL ;
609 }
610 else
611 {
612 QR = (SuiteSparseQR_factorization <Entry> *)
613 (C_QR->factors) ;
614 if (QR == NULL || QR->QRnum == NULL)
615 {
616 cc->status = CHOLMOD_OUT_OF_MEMORY ;
617 QR = NULL ;
618 }
619 else
620 {
621 // QR itself will be kept; free the C wrapper
622 C_QR->factors = NULL ;
623 cc->status = CHOLMOD_OK ;
624 if (QR == NULL) printf ("Hey!!\n") ;
625 }
626 }
627 SuiteSparseQR_C_free (&C_QR, cc) ;
628
629
630 }
631 else if (split == 3)
632 {
633
634 C_QR = SuiteSparseQR_C_factorize (ordering, tol, A, cc) ;
635 int save = cc->status ;
636 if (C_QR == NULL)
637 {
638 QR = NULL ;
639 }
640 else
641 {
642 QR = (SuiteSparseQR_factorization <Entry> *) C_QR->factors ;
643 C_QR->factors = NULL ;
644 SuiteSparseQR_C_free (&C_QR, cc) ;
645 }
646 cc->status = save ;
647
648 }
649 else if (split == 1 || split == 2)
650 {
651 // split symbolic/numeric, no singletons exploited
652 QR = SuiteSparseQR_symbolic <Entry> (ordering,
653 tol >= 0 || tol <= SPQR_DEFAULT_TOL, A, cc) ;
654 if (cc->status < CHOLMOD_OK)
655 {
656 continue ;
657 }
658 ASSERT (QR != NULL) ;
659 SuiteSparseQR_numeric <Entry> (tol, A, QR, cc) ;
660 if (cc->status < CHOLMOD_OK)
661 {
662 SuiteSparseQR_free <Entry> (&QR, cc) ;
663 }
664 }
665 else
666 {
667 QR = SuiteSparseQR_factorize <Entry> (ordering, tol, A, cc) ;
668 }
669
670 if (cc->status == CHOLMOD_OK) break ;
671 }
672 normal_memory_handler (cc) ;
673 }
674
675 if (QR == NULL) printf ("huh?? split: %d ordering %d tol %g\n", split,
676 ordering, tol) ;
677 return (QR) ;
678 }
679
680
681 #endif
682
683 // =============================================================================
684 // === SPQR_qr =================================================================
685 // =============================================================================
686
687 // wrapper for SuiteSparseQR, optionally testing memory allocation
688
SPQR_qr(int ordering,double tol,Long econ,Long getCTX,cholmod_sparse * A,cholmod_sparse * Bsparse,cholmod_dense * Bdense,cholmod_sparse ** Zsparse,cholmod_dense ** Zdense,cholmod_sparse ** R,Long ** E,cholmod_sparse ** H,Long ** HPinv,cholmod_dense ** HTau,cholmod_common * cc,int use_c_version,Long memory_test,Long memory_punt)689 template <typename Entry> Long SPQR_qr
690 (
691 // arguments for SuiteSparseQR:
692 int ordering,
693 double tol,
694 Long econ,
695 Long getCTX,
696 cholmod_sparse *A,
697 cholmod_sparse *Bsparse,
698 cholmod_dense *Bdense,
699 cholmod_sparse **Zsparse,
700 cholmod_dense **Zdense,
701 cholmod_sparse **R,
702 Long **E,
703 cholmod_sparse **H,
704 Long **HPinv,
705 cholmod_dense **HTau,
706 cholmod_common *cc,
707
708 // which version to use (C or C++)
709 int use_c_version, // if TRUE use C version, otherwise use C++
710
711 // malloc control
712 Long memory_test, // if TRUE, test malloc error handling
713 Long memory_punt // if TRUE, test punt case
714 )
715 {
716 Long rank ;
717 if (!memory_test)
718 {
719 // just call the method directly; no memory testing
720 if (use_c_version)
721 {
722 rank = SuiteSparseQR_C (ordering, tol, econ, getCTX, A,
723 Bsparse, Bdense, Zsparse, Zdense, R, E, H, HPinv, HTau, cc) ;
724 }
725 else
726 {
727 rank = SuiteSparseQR <Entry> (ordering, tol, econ, getCTX, A,
728 Bsparse, Bdense, Zsparse, Zdense, R, E, H, HPinv, HTau, cc) ;
729 }
730 }
731 else
732 {
733 // test malloc error handling
734 Long tries ;
735 test_memory_handler (cc) ;
736 my_punt = memory_punt ;
737 for (tries = 0 ; my_tries < 0 ; tries++)
738 {
739 my_tries = tries ;
740 if (use_c_version)
741 {
742 rank = SuiteSparseQR_C (ordering, tol, econ, getCTX, A,
743 Bsparse, Bdense, Zsparse, Zdense, R, E, H, HPinv, HTau, cc);
744 }
745 else
746 {
747 rank = SuiteSparseQR <Entry> (ordering, tol, econ, getCTX, A,
748 Bsparse, Bdense, Zsparse, Zdense, R, E, H, HPinv, HTau, cc);
749 }
750 if (cc->status == CHOLMOD_OK)
751 {
752 break ;
753 }
754 }
755 normal_memory_handler (cc) ;
756 }
757 return (rank) ;
758 }
759
760
761 // =============================================================================
762 // === my_rand =================================================================
763 // =============================================================================
764
765 // The POSIX example of rand, duplicated here so that the same sequence will
766 // be generated on different machines.
767
768 static unsigned long next = 1 ;
769
770 #define MY_RAND_MAX 32767
771
772 // RAND_MAX assumed to be 32767
my_rand(void)773 Long my_rand (void)
774 {
775 next = next * 1103515245 + 12345 ;
776 return ((unsigned)(next/65536) % (MY_RAND_MAX + 1)) ;
777 }
778
my_srand(unsigned seed)779 void my_srand (unsigned seed)
780 {
781 next = seed ;
782 }
783
my_seed(void)784 unsigned long my_seed (void)
785 {
786 return (next) ;
787 }
788
nrand(Long n)789 Long nrand (Long n) // return a random Long between 0 and n-1
790 {
791 return ((n <= 0) ? 0 : (my_rand ( ) % n)) ;
792 }
793
xrand()794 double xrand ( ) // return a random double between -1 and 1
795 {
796 double x = ((double) my_rand ( )) / MY_RAND_MAX ;
797 return (2*x-1) ;
798 }
799
erand(double range)800 double erand (double range)
801 {
802 return (range * xrand ( )) ;
803 }
804
erand(Complex range)805 Complex erand (Complex range)
806 {
807 /*
808 Complex x ;
809 x.real ( ) = xrand ( ) ;
810 x.imag ( ) = xrand ( ) ;
811 return (range * x) ;
812 */
813 Complex i = Complex (0,1) ;
814 return (range * (xrand ( ) + i * xrand ( ))) ;
815 }
816
817
818 // =============================================================================
819 // === getreal =================================================================
820 // =============================================================================
821
822 // return real part of a scalar x
823
getreal(double x)824 inline double getreal (double x)
825 {
826 return (x) ;
827 }
828
getreal(Complex x)829 inline double getreal (Complex x)
830 {
831 return (x.real ( )) ;
832 }
833
834 // =============================================================================
835 // === getimag =================================================================
836 // =============================================================================
837
838 // return imaginary part of a scalar x
getimag(double x)839 inline double getimag (double x) // x is an unused parameter
840 {
841 return (0) ;
842 }
843
getimag(Complex x)844 inline double getimag (Complex x)
845 {
846 return (x.imag ( )) ;
847 }
848
849
850 // =============================================================================
851 // === dense_wrapper ===========================================================
852 // =============================================================================
853
854 // place a column-oriented matrix in a cholmod_dense wrapper
855
dense_wrapper(cholmod_dense * X,Long nrow,Long ncol,Entry * Xx)856 template <typename Entry> cholmod_dense *dense_wrapper
857 (
858 cholmod_dense *X,
859 Long nrow,
860 Long ncol,
861 Entry *Xx
862 )
863 {
864 X->xtype = spqr_type <Entry> ( ) ;
865 X->nrow = nrow ;
866 X->ncol = ncol ;
867 X->d = nrow ; // leading dimension = nrow
868 X->nzmax = nrow * ncol ;
869 X->x = Xx ;
870 X->z = NULL ; // ZOMPLEX case not supported
871 X->dtype = CHOLMOD_DOUBLE ;
872 return (X) ;
873 }
874
875 // =============================================================================
876 // === sparse_split ============================================================
877 // =============================================================================
878
879 // Return the real or imaginary part of a packed complex sparse matrix
880
sparse_split(cholmod_sparse * A,Long part,cholmod_common * cc)881 cholmod_sparse *sparse_split
882 (
883 cholmod_sparse *A,
884 Long part,
885 cholmod_common *cc
886 )
887 {
888 cholmod_sparse *C ;
889 if (!A || A->xtype != CHOLMOD_COMPLEX || A->nz != NULL) return (NULL) ;
890 if (! (part == 0 || part == 1)) return (NULL) ;
891
892 Long nz = cholmod_l_nnz (A, cc) ;
893 C = cholmod_l_allocate_sparse (A->nrow, A->ncol, nz, TRUE, TRUE, 0,
894 CHOLMOD_REAL, cc) ;
895
896 Long *Ap = (Long *) A->p ;
897 Long *Ai = (Long *) A->i ;
898 double *Ax = (double *) A->x ;
899
900 Long *Cp = (Long *) C->p ;
901 Long *Ci = (Long *) C->i ;
902 double *Cx = (double *) C->x ;
903
904 Long n = A->ncol ;
905
906 for (Long k = 0 ; k < n+1 ; k++)
907 {
908 Cp [k] = Ap [k] ;
909 }
910
911 for (Long k = 0 ; k < nz ; k++)
912 {
913 Ci [k] = Ai [k] ;
914 }
915
916 for (Long k = 0 ; k < nz ; k++)
917 {
918 Cx [k] = Ax [2*k + part] ;
919 }
920
921 return (C) ;
922 }
923
sparse_real(cholmod_sparse * A,cholmod_common * cc)924 cholmod_sparse *sparse_real (cholmod_sparse *A, cholmod_common *cc)
925 {
926 return (sparse_split (A, 0, cc)) ;
927 }
928
sparse_imag(cholmod_sparse * A,cholmod_common * cc)929 cholmod_sparse *sparse_imag (cholmod_sparse *A, cholmod_common *cc)
930 {
931 return (sparse_split (A, 1, cc)) ;
932 }
933
934 // =============================================================================
935 // === sparse_merge ============================================================
936 // =============================================================================
937
938 // Add the real and imaginary parts of a matrix (both stored in real form)
939 // into a single matrix. The two parts must have the same nonzero pattern.
940 // A is CHOLMOD_REAL on input and holds the real part, it is CHOLMOD_COMPLEX
941 // on output. A_imag is CHOLMOD_REAL on input; it holds the imaginary part
942 // of A as a real matrix.
943
sparse_merge(cholmod_sparse * A,cholmod_sparse * A_imag,cholmod_common * cc)944 int sparse_merge
945 (
946 cholmod_sparse *A, // input/output
947 cholmod_sparse *A_imag, // input only
948 cholmod_common *cc
949 )
950 {
951 if (A == NULL || A_imag == NULL)
952 {
953 return (FALSE) ;
954 }
955 Long nz1 = cholmod_l_nnz (A, cc) ;
956 Long nz2 = cholmod_l_nnz (A_imag, cc) ;
957 if (A->xtype != CHOLMOD_REAL || A_imag->xtype != CHOLMOD_REAL || nz1 != nz2)
958 {
959 return (FALSE) ;
960 }
961
962 // change A from real to complex
963 cholmod_l_sparse_xtype (CHOLMOD_COMPLEX, A, cc) ;
964
965 double *Ax = (double *) A->x ;
966 double *Az = (double *) A_imag->x ;
967
968 // merge in the imaginary part from A_imag into A
969 for (Long k = 0 ; k < nz1 ; k++)
970 {
971 Ax [2*k+1] = Az [k] ;
972 }
973 return (TRUE) ;
974 }
975
976
977 // =============================================================================
978 // === sparse_diff =============================================================
979 // =============================================================================
980
981 // Compute C = A-B where A and B are either both real, or both complex
982
sparse_diff(cholmod_sparse * A,cholmod_sparse * B,cholmod_common * cc)983 template <typename Entry> cholmod_sparse *sparse_diff
984 (
985 cholmod_sparse *A,
986 cholmod_sparse *B,
987 cholmod_common *cc
988 )
989 {
990 cholmod_sparse *C ;
991 double one [2] = {1,0}, minusone [2] = {-1,0} ;
992
993 if (spqr_type <Entry> ( ) == CHOLMOD_REAL)
994 {
995 // C = A - B
996 C = cholmod_l_add (A, B, one, minusone, TRUE, TRUE, cc) ;
997 }
998 else
999 {
1000 cholmod_sparse *A_real, *A_imag, *B_real, *B_imag, *C_imag ;
1001
1002 A_real = sparse_real (A, cc) ;
1003 A_imag = sparse_imag (A, cc) ;
1004
1005 B_real = sparse_real (B, cc) ;
1006 B_imag = sparse_imag (B, cc) ;
1007
1008 // real(C) = real(A) - real (B)
1009 C = cholmod_l_add (A_real, B_real, one, minusone, TRUE, TRUE, cc) ;
1010
1011 // imag(C) = imag(A) - imag (B)
1012 C_imag = cholmod_l_add (A_imag, B_imag, one, minusone, TRUE, TRUE, cc) ;
1013
1014 // C = real(C) + 1i*imag(C)
1015 sparse_merge (C, C_imag, cc) ;
1016 cholmod_l_free_sparse (&C_imag, cc) ;
1017
1018 cholmod_l_free_sparse (&A_real, cc) ;
1019 cholmod_l_free_sparse (&A_imag, cc) ;
1020 cholmod_l_free_sparse (&B_real, cc) ;
1021 cholmod_l_free_sparse (&B_imag, cc) ;
1022 }
1023
1024 return (C) ;
1025 }
1026
1027
1028 // =============================================================================
1029 // === permute_columns =========================================================
1030 // =============================================================================
1031
1032 // compute A(:,P)
1033
permute_columns(cholmod_sparse * A,Long * P,cholmod_common * cc)1034 template <typename Entry> cholmod_sparse *permute_columns
1035 (
1036 cholmod_sparse *A,
1037 Long *P,
1038 cholmod_common *cc
1039 )
1040 {
1041 Long m = A->nrow ;
1042 Long n = A->ncol ;
1043 Long nz = cholmod_l_nnz (A, cc) ;
1044 Long xtype = spqr_type <Entry> ( ) ;
1045 Long *Ap = (Long *) A->p ;
1046 Long *Ai = (Long *) A->i ;
1047 Entry *Ax = (Entry *) A->x ;
1048 cholmod_sparse *C ;
1049
1050 // allocate empty matrix C with space for nz entries
1051 C = cholmod_l_allocate_sparse (m, n, nz, TRUE, TRUE, 0, xtype, cc) ;
1052 Long *Cp = (Long *) C->p ;
1053 Long *Ci = (Long *) C->i ;
1054 Entry *Cx = (Entry *) C->x ;
1055
1056 // construct column pointers for C
1057 for (Long k = 0 ; k < n ; k++)
1058 {
1059 // column j of A becomes column k of C
1060 Long j = P ? P [k] : k ;
1061 Cp [k] = Ap [j+1] - Ap [j] ;
1062 }
1063 spqr_cumsum (n, Cp) ;
1064
1065 // copy columns from A to C
1066 for (Long k = 0 ; k < n ; k++)
1067 {
1068 // copy column k of A into column j of C
1069 Long j = P ? P [k] : k ;
1070 Long pdest = Cp [k] ;
1071 Long psrc = Ap [j] ;
1072 Long len = Ap [j+1] - Ap [j] ;
1073 for (Long t = 0 ; t < len ; t++)
1074 {
1075 Ci [pdest + t] = Ai [psrc + t] ;
1076 Cx [pdest + t] = Ax [psrc + t] ;
1077 }
1078 }
1079
1080 return (C) ;
1081 }
1082
1083
1084 // =============================================================================
1085 // === sparse_multiply =========================================================
1086 // =============================================================================
1087
1088 // compute A*B where A and B can be both real or both complex
1089
sparse_multiply(cholmod_sparse * A,cholmod_sparse * B,cholmod_common * cc)1090 template <typename Entry> cholmod_sparse *sparse_multiply
1091 (
1092 cholmod_sparse *A,
1093 cholmod_sparse *B,
1094 cholmod_common *cc
1095 )
1096 {
1097 cholmod_sparse *C ;
1098
1099 if (spqr_type <Entry> ( ) == CHOLMOD_REAL)
1100 {
1101 // C = A*B
1102 C = cholmod_l_ssmult (A, B, 0, TRUE, TRUE, cc) ;
1103 }
1104 else
1105 {
1106 // cholmod_ssmult and cholmod_add only work for real matrices
1107 cholmod_sparse *A_real, *A_imag, *B_real, *B_imag, *C_imag, *T1, *T2 ;
1108 double one [2] = {1,0}, minusone [2] = {-1,0} ;
1109
1110 A_real = sparse_real (A, cc) ;
1111 A_imag = sparse_imag (A, cc) ;
1112
1113 B_real = sparse_real (B, cc) ;
1114 B_imag = sparse_imag (B, cc) ;
1115
1116 // real(C) = real(A)*real(B) - imag(A)*imag(B)
1117 T1 = cholmod_l_ssmult (A_real, B_real, 0, TRUE, TRUE, cc) ;
1118 T2 = cholmod_l_ssmult (A_imag, B_imag, 0, TRUE, TRUE, cc) ;
1119 C = cholmod_l_add (T1, T2, one, minusone, TRUE, TRUE, cc) ;
1120 cholmod_l_free_sparse (&T1, cc) ;
1121 cholmod_l_free_sparse (&T2, cc) ;
1122
1123 // imag(C) = imag(A)*real(B) + real(A)*imag(B)
1124 T1 = cholmod_l_ssmult (A_imag, B_real, 0, TRUE, TRUE, cc) ;
1125 T2 = cholmod_l_ssmult (A_real, B_imag, 0, TRUE, TRUE, cc) ;
1126 C_imag = cholmod_l_add (T1, T2, one, one, TRUE, TRUE, cc) ;
1127 cholmod_l_free_sparse (&T1, cc) ;
1128 cholmod_l_free_sparse (&T2, cc) ;
1129
1130 // C = real(C) + 1i*imag(C)
1131 sparse_merge (C, C_imag, cc) ;
1132 cholmod_l_free_sparse (&C_imag, cc) ;
1133
1134 cholmod_l_free_sparse (&A_real, cc) ;
1135 cholmod_l_free_sparse (&A_imag, cc) ;
1136 cholmod_l_free_sparse (&B_real, cc) ;
1137 cholmod_l_free_sparse (&B_imag, cc) ;
1138 }
1139
1140 return (C) ;
1141 }
1142
1143
1144 // =============================================================================
1145 // === sparse_resid ============================================================
1146 // =============================================================================
1147
1148 // compute norm (A*x-b,1) for A,x, and b all sparse
1149
sparse_resid(cholmod_sparse * A,double anorm,cholmod_sparse * X,cholmod_sparse * B,cholmod_common * cc)1150 template <typename Entry> double sparse_resid
1151 (
1152 cholmod_sparse *A,
1153 double anorm,
1154 cholmod_sparse *X,
1155 cholmod_sparse *B,
1156 cholmod_common *cc
1157 )
1158 {
1159 cholmod_sparse *AX, *Resid ;
1160 // AX = A*X
1161 AX = sparse_multiply <Entry> (A, X, cc) ;
1162 // Resid = AX - B
1163 Resid = sparse_diff <Entry> (AX, B, cc) ;
1164 // resid = norm (Resid,1)
1165 double resid = cholmod_l_norm_sparse (Resid, 1, cc) ;
1166 resid = CHECK_NAN (resid) ;
1167 cholmod_l_free_sparse (&AX, cc) ;
1168 cholmod_l_free_sparse (&Resid, cc) ;
1169 return (CHECK_NAN (resid / anorm)) ;
1170 }
1171
1172
1173 // =============================================================================
1174 // === dense_resid =============================================================
1175 // =============================================================================
1176
1177 // compute norm (A*x-b,1) for A sparse, x and b dense
1178
dense_resid(cholmod_sparse * A,double anorm,cholmod_dense * X,Long nb,Entry * Bx,cholmod_common * cc)1179 template <typename Entry> double dense_resid
1180 (
1181 cholmod_sparse *A,
1182 double anorm,
1183 cholmod_dense *X,
1184 Long nb,
1185 Entry *Bx,
1186 cholmod_common *cc
1187 )
1188 {
1189 cholmod_dense *B, Bmatrix, *Resid ;
1190 double one [2] = {1,0}, minusone [2] = {-1,0} ;
1191
1192 B = dense_wrapper (&Bmatrix, A->nrow, nb, Bx) ;
1193 // Resid = B
1194 Resid = cholmod_l_copy_dense (B, cc) ;
1195
1196 // Resid = A*X - Resid
1197 cholmod_l_sdmult (A, FALSE, one, minusone, X, Resid, cc) ;
1198
1199 // resid = norm (Resid,1)
1200 double resid = cholmod_l_norm_dense (Resid, 1, cc) ;
1201 resid = CHECK_NAN (resid) ;
1202 cholmod_l_free_dense (&Resid, cc) ;
1203 return (CHECK_NAN (resid / anorm)) ;
1204 }
1205
1206 // =============================================================================
1207 // === check_r_factor ==========================================================
1208 // =============================================================================
1209
1210 // compute norm (R'*R - (A(:,P))'*(A(:,P)), 1) / norm (A'*A,1)
1211
check_r_factor(cholmod_sparse * R,cholmod_sparse * A,Long * P,cholmod_common * cc)1212 template <typename Entry> double check_r_factor
1213 (
1214 cholmod_sparse *R,
1215 cholmod_sparse *A,
1216 Long *P,
1217 cholmod_common *cc
1218 )
1219 {
1220 cholmod_sparse *RTR, *RT, *C, *CT, *CTC, *D ;
1221
1222 // RTR = R'*R
1223 RT = cholmod_l_transpose (R, 2, cc) ;
1224 RTR = sparse_multiply <Entry> (RT, R, cc) ;
1225 cholmod_l_free_sparse (&RT, cc) ;
1226
1227 // C = A(:,P)
1228 C = permute_columns<Entry> (A, P, cc) ;
1229
1230 // CTC = C'*C
1231 CT = cholmod_l_transpose (C, 2, cc) ;
1232 CTC = sparse_multiply <Entry> (CT, C, cc) ;
1233 cholmod_l_free_sparse (&CT, cc) ;
1234 cholmod_l_free_sparse (&C, cc) ;
1235
1236 double ctcnorm = cholmod_l_norm_sparse (CTC, 1, cc) ;
1237 if (ctcnorm == 0) ctcnorm = 1 ;
1238 ctcnorm = CHECK_NAN (ctcnorm) ;
1239
1240 // D = RTR - CTC
1241 D = sparse_diff <Entry> (RTR, CTC, cc) ;
1242 cholmod_l_free_sparse (&CTC, cc) ;
1243 cholmod_l_free_sparse (&RTR, cc) ;
1244
1245 // err = norm (D,1)
1246 double err = cholmod_l_norm_sparse (D, 1, cc) / ctcnorm ;
1247 err = CHECK_NAN (err) ;
1248
1249 cholmod_l_free_sparse (&D, cc) ;
1250 return (CHECK_NAN (err)) ;
1251 }
1252
1253
1254 // =============================================================================
1255 // === check_qr ================================================================
1256 // =============================================================================
1257
1258 // compute norm (Q*R - A(:,P)) / norm (A)
1259
check_qr(cholmod_sparse * Q,cholmod_sparse * R,cholmod_sparse * A,Long * P,double anorm,cholmod_common * cc)1260 template <typename Entry> double check_qr
1261 (
1262 cholmod_sparse *Q,
1263 cholmod_sparse *R,
1264 cholmod_sparse *A,
1265 Long *P,
1266 double anorm,
1267 cholmod_common *cc
1268 )
1269 {
1270 cholmod_sparse *QR, *C, *D ;
1271
1272 // C = A(:,P)
1273 C = permute_columns<Entry> (A, P, cc) ;
1274
1275 // QR = Q*R
1276 QR = sparse_multiply <Entry> (Q, R, cc) ;
1277
1278 // D = RTR - CTC
1279 D = sparse_diff <Entry> (QR, C, cc) ;
1280 cholmod_l_free_sparse (&QR, cc) ;
1281 cholmod_l_free_sparse (&C, cc) ;
1282
1283 // err = norm (D,1)
1284 double err = cholmod_l_norm_sparse (D, 1, cc) / anorm ;
1285 err = CHECK_NAN (err) ;
1286
1287 cholmod_l_free_sparse (&D, cc) ;
1288 return (CHECK_NAN (err)) ;
1289 }
1290
1291
1292 // =============================================================================
1293 // === Rsolve ==================================================================
1294 // =============================================================================
1295
Rsolve(Long n,cholmod_sparse * R,Entry * X,Long nx,cholmod_common * cc)1296 template <typename Entry> int Rsolve
1297 (
1298 // R is n-by-n, upper triangular with zero-free diagonal
1299 Long n,
1300 cholmod_sparse *R,
1301 Entry *X, // X is n-by-nx, leading dimension n, overwritten with soln
1302 Long nx,
1303 cholmod_common *cc
1304 )
1305 {
1306 // Long n = R->n ;
1307 Long *Rp = (Long *) R->p ;
1308 Long *Ri = (Long *) R->i ;
1309 Entry *Rx = (Entry *) R->x ;
1310
1311 // check the diagonal
1312 for (Long j = 0 ; j < n ; j++)
1313 {
1314 if (Rp [j] == Rp [j+1] || Ri [Rp [j+1]-1] != j)
1315 {
1316 printf ("Rsolve: R not upper triangular w/ zero-free diagonal\n") ;
1317 return (FALSE) ;
1318 }
1319 }
1320
1321 // do the backsolve
1322 for (Long k = 0 ; k < nx ; k++)
1323 {
1324 for (Long j = n-1 ; j >= 0 ; j--)
1325 {
1326 Entry rjj = Rx [Rp [j+1]-1] ;
1327 if (rjj == (Entry) 0)
1328 {
1329 printf ("Rsolve: R has an explicit zero on the diagonal\n") ;
1330 return (FALSE) ;
1331 }
1332 X [j] /= rjj ;
1333 for (Long p = Rp [j] ; p < Rp [j+1]-1 ; p++)
1334 {
1335 X [Ri [p]] -= Rx [p] * X [j] ;
1336 }
1337 }
1338 X += n ;
1339 }
1340
1341 return (TRUE) ;
1342 }
1343
1344
1345 // =============================================================================
1346 // === create_Q ================================================================
1347 // =============================================================================
1348
1349 // create a sparse Q
create_Q(cholmod_sparse * H,cholmod_dense * HTau,Long * HPinv,cholmod_common * cc)1350 template <typename Entry> cholmod_sparse *create_Q
1351 (
1352 cholmod_sparse *H,
1353 cholmod_dense *HTau,
1354 Long *HPinv,
1355 cholmod_common *cc
1356 )
1357 {
1358 cholmod_sparse *Q, *I ;
1359 Long m = H->nrow ;
1360 Long xtype = spqr_type <Entry> ( ) ;
1361 I = cholmod_l_speye (m, m, xtype, cc) ;
1362 Q = SPQR_qmult <Entry> (1, H, HTau, HPinv, I, cc, m<300, nrand (2)) ;
1363 cholmod_l_free_sparse (&I, cc) ;
1364 return (Q) ;
1365 }
1366
1367
1368 // =============================================================================
1369 // === QRsolve =================================================================
1370 // =============================================================================
1371
1372 // solve Ax=b using H, R, and E
1373
QRsolve(cholmod_sparse * A,double anorm,Long rank,Long method,cholmod_sparse * H,cholmod_dense * HTau,Long * HPinv,cholmod_sparse * R,Long * Qfill,cholmod_dense * Bdense,cholmod_common * cc)1374 template <typename Entry> double QRsolve
1375 (
1376 cholmod_sparse *A,
1377 double anorm,
1378 Long rank,
1379 Long method,
1380 cholmod_sparse *H,
1381 cholmod_dense *HTau,
1382 Long *HPinv,
1383 cholmod_sparse *R,
1384 Long *Qfill,
1385 cholmod_dense *Bdense,
1386 cholmod_common *cc
1387 )
1388 {
1389 double one [2] = {1,0}, zero [2] = {0,0}, resid = EMPTY ;
1390 Long xtype = spqr_type <Entry> ( ) ;
1391 Long n = A->ncol ;
1392 Long m = A->nrow ;
1393 Long nrhs = Bdense->ncol ;
1394 Entry *X, *Y = NULL, *B ;
1395 cholmod_dense *Ydense = NULL ;
1396 cholmod_dense *Xdense ;
1397
1398 B = (Entry *) Bdense->x ;
1399 Xdense = cholmod_l_zeros (n, nrhs, xtype, cc) ;
1400 X = (Entry *) Xdense->x ;
1401
1402 if (method == 0)
1403 {
1404 // solve Ax=b using H, R, and E
1405 // Y = Q'*B
1406 Ydense = SPQR_qmult <Entry> (0, H, HTau, HPinv, Bdense, cc,
1407 m < 300, nrand (2)) ;
1408 }
1409 else
1410 {
1411 cholmod_sparse *Q, *QT ;
1412 // solve using Q instead of qmult
1413 Q = create_Q <Entry> (H, HTau, HPinv, cc) ;
1414 QT = cholmod_l_transpose (Q, 2, cc) ;
1415 // Y = Q'*B
1416 Ydense = cholmod_l_zeros (m, nrhs, xtype, cc) ;
1417 cholmod_l_sdmult (QT, FALSE, one, zero, Bdense, Ydense, cc) ;
1418 cholmod_l_free_sparse (&Q, cc) ;
1419 cholmod_l_free_sparse (&QT, cc) ;
1420 }
1421
1422 // Y (1:rank) = R (1:rank,1:rank) \ Y (1:rank)
1423 Y = (Entry *) Ydense->x ;
1424 Long ok = Rsolve (rank, R, Y, nrhs, cc) ;
1425 // X = E*Y
1426 if (ok)
1427 {
1428 for (Long kk = 0 ; kk < nrhs ; kk++)
1429 {
1430 for (Long k = 0 ; k < rank ; k++)
1431 {
1432 Long j = Qfill ? Qfill [k] : k ;
1433 X [j] = Y [k] ;
1434 }
1435 X += n ;
1436 Y += m ;
1437 }
1438 // check norm (A*x-b), x and b dense
1439 resid = dense_resid (A, anorm, Xdense, nrhs, B, cc) ;
1440 }
1441
1442 cholmod_l_free_dense (&Ydense, cc) ;
1443 cholmod_l_free_dense (&Xdense, cc) ;
1444 return (CHECK_NAN (resid)) ;
1445 }
1446
1447
1448 // =============================================================================
1449 // === check_qmult =============================================================
1450 // =============================================================================
1451
1452 // Test qmult
1453
check_qmult(cholmod_sparse * H,cholmod_dense * HTau,Long * HPinv,Long test_errors,cholmod_common * cc)1454 template <typename Entry> double check_qmult
1455 (
1456 cholmod_sparse *H,
1457 cholmod_dense *HTau,
1458 Long *HPinv,
1459 Long test_errors,
1460 cholmod_common *cc
1461 )
1462 {
1463 cholmod_sparse *Q, *QT, *Xsparse, *Ssparse, *Zsparse ;
1464 cholmod_dense *Xdense, *Zdense, *Sdense, *Ydense ;
1465 Long xtype = spqr_type <Entry> ( ) ;
1466 Entry *X, *Y, *Z, *S ;
1467 double err, maxerr = 0 ;
1468 double one [2] = {1,0}, zero [2] = {0,0} ;
1469 Entry range = (Entry) 1.0 ;
1470 Long k ;
1471
1472 Long m = H->nrow ;
1473 Q = create_Q <Entry> (H, HTau, HPinv, cc) ; // construct Q from H
1474
1475 QT = cholmod_l_transpose (Q, 2, cc) ; // QT = Q'
1476
1477 // compare Q with qmult for sparse and dense X
1478 for (Long nx = 0 ; nx < 5 ; nx++) // # of columns of X
1479 {
1480 Long xsize = m * nx ; // size of X
1481 for (Long nz = 1 ; nz <= xsize+1 ; nz *= 16) // # of nonzeros in X
1482 {
1483
1484 // -----------------------------------------------------------------
1485 // create X as m-by-nx, both sparse and dense
1486 // -----------------------------------------------------------------
1487
1488 Xdense = cholmod_l_zeros (m, nx, xtype, cc) ;
1489 X = (Entry *) Xdense->x ;
1490 for (k = 0 ; k < nz ; k++)
1491 {
1492 X [nrand (xsize)] += erand (range) ;
1493 }
1494 Xsparse = cholmod_l_dense_to_sparse (Xdense, TRUE, cc) ;
1495
1496 // -----------------------------------------------------------------
1497 // Y = Q'*X for method 0, Y = Q*X for method 1
1498 // -----------------------------------------------------------------
1499
1500 for (int method = 0 ; method <= 1 ; method++)
1501 {
1502 // Y = Q'*X or Q*X
1503 Ydense = SPQR_qmult <Entry> (method, H, HTau, HPinv, Xdense, cc,
1504 m < 300, nrand (2)) ;
1505 Y = (Entry *) Ydense->x ;
1506
1507 Zdense = cholmod_l_zeros (m, nx, xtype, cc) ;
1508 cholmod_l_sdmult (Q, (method == 0), one, zero,
1509 Xdense, Zdense, cc) ;
1510 Z = (Entry *) Zdense->x ;
1511
1512 for (err = 0, k = 0 ; k < xsize ; k++)
1513 {
1514 double e1 = spqr_abs (Y [k] - Z [k], cc) ;
1515 e1 = CHECK_NAN (e1) ;
1516 err = MAX (err, e1) ;
1517 }
1518 maxerr = MAX (maxerr, err) ;
1519
1520 // S = Q'*Xsparse or Q*Xsparse
1521 Ssparse = SPQR_qmult <Entry> (
1522 method, H, HTau, HPinv, Xsparse, cc, m < 300, nrand (2)) ;
1523 Sdense = cholmod_l_sparse_to_dense (Ssparse, cc) ;
1524 S = (Entry *) Sdense->x ;
1525
1526 for (err = 0, k = 0 ; k < xsize ; k++)
1527 {
1528 double e1 = spqr_abs (S [k] - Y [k], cc) ;
1529 e1 = CHECK_NAN (e1) ;
1530 err = MAX (err, e1) ;
1531 }
1532 maxerr = MAX (maxerr, err) ;
1533
1534 cholmod_l_free_dense (&Ydense, cc) ;
1535 cholmod_l_free_dense (&Zdense, cc) ;
1536 cholmod_l_free_sparse (&Ssparse, cc) ;
1537 cholmod_l_free_dense (&Sdense, cc) ;
1538 }
1539
1540 cholmod_l_free_dense (&Xdense, cc) ;
1541 cholmod_l_free_sparse (&Xsparse, cc) ;
1542
1543 // -----------------------------------------------------------------
1544 // create X as nx-by-m, both sparse and dense
1545 // -----------------------------------------------------------------
1546
1547 Xdense = cholmod_l_zeros (nx, m, xtype, cc) ;
1548 X = (Entry *) Xdense->x ;
1549 for (k = 0 ; k < nz ; k++)
1550 {
1551 X [nrand (xsize)] += erand (range) ;
1552 }
1553 Xsparse = cholmod_l_dense_to_sparse (Xdense, TRUE, cc) ;
1554
1555 // -----------------------------------------------------------------
1556 // Y = X*Q' for method 2, Y = X*Q for method 3
1557 // -----------------------------------------------------------------
1558
1559 for (int method = 2 ; method <= 3 ; method++)
1560 {
1561 // Y = X*Q' or X*Q
1562 Ydense = SPQR_qmult <Entry> (method, H, HTau, HPinv, Xdense, cc,
1563 m < 300, nrand (2)) ;
1564 Y = (Entry *) Ydense->x ;
1565
1566 if (method == 2)
1567 {
1568 // Zsparse = (X*Q')
1569 Zsparse = sparse_multiply <Entry> (Xsparse, QT, cc) ;
1570 }
1571 else
1572 {
1573 // Zsparse = (X*Q)
1574 Zsparse = sparse_multiply <Entry> (Xsparse, Q, cc) ;
1575 }
1576 Zdense = cholmod_l_sparse_to_dense (Zsparse, cc) ;
1577
1578 Z = (Entry *) Zdense->x ;
1579
1580 for (err = 0, k = 0 ; k < xsize ; k++)
1581 {
1582 double e1 = spqr_abs (Y [k] - Z [k], cc) ;
1583 e1 = CHECK_NAN (e1) ;
1584 err = MAX (err, e1) ;
1585 }
1586 maxerr = MAX (maxerr, err) ;
1587
1588 // S = X*Q' or X*Q
1589 Ssparse = SPQR_qmult <Entry> (
1590 method, H, HTau, HPinv, Xsparse, cc, m < 300, nrand (2)) ;
1591 Sdense = cholmod_l_sparse_to_dense (Ssparse, cc) ;
1592 S = (Entry *) Sdense->x ;
1593
1594 for (err = 0, k = 0 ; k < xsize ; k++)
1595 {
1596 double e1 = spqr_abs (S [k] - Y [k], cc) ;
1597 e1 = CHECK_NAN (e1) ;
1598 err = MAX (err, e1) ;
1599 }
1600 maxerr = MAX (maxerr, err) ;
1601
1602 cholmod_l_free_dense (&Ydense, cc) ;
1603 cholmod_l_free_dense (&Zdense, cc) ;
1604 cholmod_l_free_sparse (&Ssparse, cc) ;
1605 cholmod_l_free_sparse (&Zsparse, cc) ;
1606 cholmod_l_free_dense (&Sdense, cc) ;
1607 }
1608
1609 cholmod_l_free_dense (&Xdense, cc) ;
1610 cholmod_l_free_sparse (&Xsparse, cc) ;
1611
1612 }
1613 }
1614 cholmod_l_free_sparse (&Q, cc) ;
1615 cholmod_l_free_sparse (&QT, cc) ;
1616
1617 // -------------------------------------------------------------------------
1618 // qmult error conditions
1619 // -------------------------------------------------------------------------
1620
1621 // These should fail; expect 6 error messages in the output
1622
1623 if (test_errors)
1624 {
1625 err = 0 ;
1626 printf ("The following six errors are expected:\n") ;
1627 Xdense = cholmod_l_zeros (m+1, 1, xtype,cc) ;
1628 Ydense = SuiteSparseQR_qmult <Entry> (0, H, HTau, HPinv, Xdense, cc) ;
1629 if (Ydense != NULL || cc->status != CHOLMOD_INVALID) err++ ;
1630 cholmod_l_free_dense (&Xdense, cc) ;
1631
1632 Xdense = cholmod_l_zeros (1, m+1, xtype,cc) ;
1633 Ydense = SuiteSparseQR_qmult <Entry> (2, H, HTau, HPinv, Xdense, cc) ;
1634 if (Ydense != NULL || cc->status != CHOLMOD_INVALID) err++ ;
1635 Ydense = SuiteSparseQR_qmult <Entry> (42, H, HTau, HPinv, Xdense, cc) ;
1636 if (Ydense != NULL || cc->status != CHOLMOD_INVALID) err++ ;
1637 cholmod_l_free_dense (&Xdense, cc) ;
1638
1639 Xsparse = cholmod_l_speye (m+1, m+1, xtype, cc) ;
1640
1641 Q = SuiteSparseQR_qmult <Entry> (0, H, HTau, HPinv, Xsparse, cc);
1642 if (Q != NULL || cc->status != CHOLMOD_INVALID) err++ ;
1643 Q = SuiteSparseQR_qmult <Entry> (2, H, HTau, HPinv, Xsparse, cc);
1644 if (Q != NULL || cc->status != CHOLMOD_INVALID) err++ ;
1645 Q = SuiteSparseQR_qmult <Entry> (9, H, HTau, HPinv, Xsparse, cc);
1646 if (Q != NULL || cc->status != CHOLMOD_INVALID) err++ ;
1647
1648 printf (" ... error handling done\n\n") ;
1649 cholmod_l_free_sparse (&Xsparse, cc) ;
1650
1651 maxerr = MAX (maxerr, err) ;
1652 }
1653
1654 return (CHECK_NAN (maxerr)) ;
1655 }
1656
1657
1658 // =============================================================================
1659 // === check_rc ================================================================
1660 // =============================================================================
1661
1662 // X = Q'*B has been done, continue with C=R\C and
1663
check_rc(Long rank,cholmod_sparse * R,cholmod_sparse * A,Entry * B,cholmod_dense * X,Long nrhs,double anorm,Long * Qfill,cholmod_common * cc)1664 template <typename Entry> double check_rc
1665 (
1666 Long rank,
1667 cholmod_sparse *R,
1668 cholmod_sparse *A,
1669 Entry *B,
1670 cholmod_dense *X,
1671 Long nrhs,
1672 double anorm,
1673 Long *Qfill,
1674 cholmod_common *cc
1675 )
1676 {
1677 double resid = EMPTY ;
1678 Long xtype = spqr_type <Entry> ( ) ;
1679 cholmod_dense *W ;
1680 Long n, ok ;
1681 Entry *W1, *X1 ;
1682 if (!R || !X)
1683 {
1684 ok = 0 ;
1685 }
1686 else
1687 {
1688 n = X->nrow ;
1689 X1 = (Entry *) X->x ;
1690 // solve X = R\X, overwriting X with solution
1691 ok = Rsolve (rank, R, X1, nrhs, cc) ;
1692 }
1693 if (ok)
1694 {
1695 // W = E*X
1696 // W = (Entry *) cholmod_l_calloc (A->ncol * nrhs, sizeof (Entry), cc) ;
1697 W = cholmod_l_zeros (A->ncol, nrhs, xtype, cc) ;
1698 W1 = (Entry *) W->x ;
1699 for (Long col = 0 ; col < nrhs ; col++)
1700 {
1701 for (Long k = 0 ; k < rank ; k++)
1702 {
1703 Long j = Qfill ? Qfill [k] : k ;
1704 if (j < (Long) A->ncol) W1 [j] = X1 [k] ;
1705 }
1706 W1 += A->ncol ;
1707 X1 += n ;
1708 }
1709 // check norm (A*x-b), x and b dense
1710 resid = dense_resid (A, anorm, W, nrhs, B, cc) ;
1711 // cholmod_l_free (A->ncol * nrhs, sizeof (Entry), W, cc) ;
1712 cholmod_l_free_dense (&W, cc) ;
1713 }
1714 return (CHECK_NAN (resid)) ;
1715 }
1716
1717
1718 // =============================================================================
1719 // === transpose ===============================================================
1720 // =============================================================================
1721
1722 // Transpose a dense matrix.
1723
transpose(cholmod_dense * Xdense,cholmod_common * cc)1724 template <typename Entry> cholmod_dense *transpose
1725 (
1726 cholmod_dense *Xdense,
1727 cholmod_common *cc
1728 )
1729 {
1730 Entry *X, *Y ;
1731 cholmod_dense *Ydense ;
1732 if (Xdense == NULL)
1733 {
1734 printf ("transpose failed!\n") ;
1735 return (NULL) ;
1736 }
1737 Long m = Xdense->nrow ;
1738 Long n = Xdense->ncol ;
1739 Long ldx = Xdense->d ;
1740 Long xtype = spqr_type <Entry> ( ) ;
1741 Ydense = cholmod_l_allocate_dense (n, m, n, xtype, cc) ;
1742 X = (Entry *) Xdense->x ;
1743 Y = (Entry *) Ydense->x ;
1744 for (Long i = 0 ; i < m ; i++)
1745 {
1746 for (Long j = 0 ; j < n ; j++)
1747 {
1748 Y [j+i*n] = spqr_conj (X [i+j*ldx]) ;
1749 }
1750 }
1751 return (Ydense) ;
1752 }
1753
1754 // =============================================================================
1755 // === qrtest ==================================================================
1756 // =============================================================================
1757
qrtest(cholmod_sparse * A,double errs[5],cholmod_common * cc)1758 template <typename Entry> void qrtest
1759 (
1760 cholmod_sparse *A,
1761 double errs [5],
1762 cholmod_common *cc
1763 )
1764 {
1765 cholmod_sparse *H, *I, *R, *Q, *Csparse, *Xsparse, *AT, *Bsparse ;
1766 cholmod_dense *Cdense, *Xdense, *Bdense, *HTau ; ;
1767 double tol = DBL_EPSILON, err, resid, maxerr, maxresid [2][2] ;
1768 double tols [ ] = { SPQR_DEFAULT_TOL, -1, 0, DBL_EPSILON } ;
1769 Long n, m, nz, *HPinv, ntol, *Ai, *Ap, k, *Qfill, rank, nb, *Cp, *Ci, econ,
1770 which ;
1771 Entry *B, *Ax, *Cx ;
1772 Long xtype = spqr_type <Entry> ( ) ;
1773 int ordering ;
1774 Entry range = (Entry) 1.0 ;
1775
1776 errs [0] = EMPTY ;
1777 errs [1] = EMPTY ;
1778 errs [2] = EMPTY ;
1779 errs [3] = EMPTY ;
1780 errs [4] = EMPTY ;
1781 if (A == NULL)
1782 {
1783 fprintf (stderr, "qrtest: no input matrix\n") ;
1784 return ;
1785 }
1786
1787 m = A->nrow ;
1788 n = A->ncol ;
1789 Ap = (Long *) A->p ;
1790 Ai = (Long *) A->i ;
1791 Ax = (Entry *) A->x ;
1792 double anorm = cholmod_l_norm_sparse (A, 1, cc) ;
1793 anorm = CHECK_NAN (anorm) ;
1794 printf ("\n===========================================================\n") ;
1795 printf ("Matrix: %ld by %ld, nnz(A) = %ld, norm(A,1) = %g\n",
1796 m, n, cholmod_l_nnz (A, cc), anorm) ;
1797 printf ( "===========================================================\n") ;
1798
1799 if (anorm == 0) anorm = 1 ;
1800
1801 // these should all be zero, no matter what the matrix
1802 maxerr = 0 ;
1803
1804 // residuals for well-determined or under-determined systems. If
1805 // not rank deficient, these should be zero
1806 maxresid [0][0] = 0 ; // for m <= n, default tol, ordering not fixed
1807 maxresid [0][1] = 0 ; // for m <= n, all other cases
1808
1809 // residuals for least-squares systems (these will not be zero)
1810 maxresid [1][0] = 0 ; // for m > n, default tol, ordering not fixed
1811 maxresid [1][1] = 0 ; // for m > n, all other cases
1812
1813 my_srand (m+n) ;
1814
1815 if (m > 45000)
1816 {
1817 // The only thing returned are the statistics (rank, etc)
1818 printf ("\n=== QR huge (expect int overflow):\n") ;
1819 rank = SPQR_qr <Entry> (
1820 0, 0, 0, 0, A,
1821 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
1822 cc, FALSE, FALSE, FALSE) ;
1823 return ;
1824 }
1825
1826 if (MAX (m,n) >= 300) fprintf (stderr, "please wait ... ") ;
1827
1828 AT = cholmod_l_transpose (A, 2, cc) ;
1829
1830 // -------------------------------------------------------------------------
1831 // test QR routines
1832 // -------------------------------------------------------------------------
1833
1834 econ = m ;
1835
1836 for (ordering = 0 ; ordering <= 9 ; ordering++)
1837 {
1838
1839 // skip SPQR_ORDERING_GIVEN, unless the matrix is tiny
1840 if (ordering == SPQR_ORDERING_GIVEN && MAX (m,n) > 10) continue ;
1841
1842 for (ntol = 0 ; ntol < NTOL ; ntol++)
1843 {
1844
1845 tol = tols [ntol] ;
1846 if // (ntol == 0) // this old test is fragile ...
1847 (tol == SPQR_DEFAULT_TOL) // use this instead
1848 {
1849 // with default tolerance, the fixed ordering can sometimes
1850 // fail if the matrix is rank deficient (R cannot be permuted
1851 // to upper trapezoidal form).
1852 which = (ordering == 0) ;
1853 }
1854 else
1855 {
1856 // with non-default tolerance, the solution can sometimes be
1857 // poor; this is expected.
1858 which = 1 ;
1859 }
1860 printf ("\n=== QR with ordering %d tol %g:\n", ordering, tol) ;
1861
1862 // -----------------------------------------------------------------
1863 // create dense and sparse right-hand-sides
1864 // -----------------------------------------------------------------
1865
1866 nb = 5 ;
1867 Bdense = cholmod_l_zeros (m, nb, xtype, cc) ;
1868 B = (Entry *) Bdense->x ;
1869 for (k = 0 ; k < m*nb ; k++)
1870 {
1871 B [k] = ((double) (my_rand ( ) % 2)) * erand (range) ;
1872 }
1873 Bsparse = cholmod_l_dense_to_sparse (Bdense, TRUE, cc) ;
1874
1875 // -----------------------------------------------------------------
1876 // X = qrsolve(A,B) where X and B are dense
1877 // -----------------------------------------------------------------
1878
1879 // X = A\B
1880 if (ordering == SPQR_ORDERING_DEFAULT && tol == SPQR_DEFAULT_TOL)
1881 {
1882 printf ("[ backslach, A and B and X dense: defaults\n") ;
1883 Xdense = SuiteSparseQR <Entry> (A, Bdense, cc) ;
1884 printf ("] done backslach, A and B and X dense: defaults\n") ;
1885 }
1886 else
1887 {
1888 printf ("[ backslach, A and B and X dense: tol %g order %d\n",
1889 tol, ordering) ;
1890 Xdense = SuiteSparseQR <Entry> (ordering, tol, A, Bdense, cc) ;
1891 printf ("] done backslach, A B X dense: tol %g order %d\n",
1892 tol, ordering) ;
1893 }
1894
1895 // check norm (A*x-b), x and b dense
1896 resid = dense_resid (A, anorm, Xdense, nb, B, cc) ;
1897 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
1898 printf ("Resid0b %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
1899
1900 cholmod_l_free_dense (&Xdense, cc) ;
1901
1902 if (cc->useGPU)
1903 {
1904 // error testing for infeasible GPU memory
1905 Long save = cc->gpuMemorySize ;
1906 cc->gpuMemorySize = 1 ;
1907 printf ("[ Pretend GPU memory is too small:\n") ;
1908 Xdense = SuiteSparseQR <Entry> (ordering, tol, A, Bdense, cc) ;
1909 cc->gpuMemorySize = save ;
1910 printf ("] test done infeasible GPU, status %2d, useGPU: %d\n",
1911 cc->status, cc->useGPU) ;
1912 cholmod_l_free_dense (&Xdense, cc) ;
1913 }
1914
1915 cholmod_l_free_dense (&Bdense, cc) ;
1916
1917 // -----------------------------------------------------------------
1918 // X = qrsolve(A,B) where X and B are sparse
1919 // -----------------------------------------------------------------
1920
1921 // X = A\B
1922 printf ("[ backslash with sparse B: tol %g\n", tol) ;
1923 Xsparse = SuiteSparseQR <Entry> (ordering, tol, A, Bsparse, cc) ;
1924 printf ("] did tol %g\n", tol) ;
1925
1926 // check norm (A*x-b), x and b sparse
1927 resid = sparse_resid <Entry> (A, anorm, Xsparse, Bsparse, cc) ;
1928 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
1929 printf ("Resid0 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
1930
1931 cholmod_l_free_sparse (&Xsparse, cc) ;
1932 cholmod_l_free_sparse (&Bsparse, cc) ;
1933
1934 // -----------------------------------------------------------------
1935 // X = qrsolve (A,B) where X and B are sparse, with memory test
1936 // -----------------------------------------------------------------
1937
1938 // use B = A and solve AX=B where X is sparse
1939 cc->SPQR_shrink = 0 ; // shrink = 0 ;
1940 rank = SPQR_qr <Entry> (
1941 ordering, tol, econ, 2, A,
1942 A, NULL, &Xsparse, NULL, NULL, &Qfill, NULL, NULL, NULL,
1943 cc, TRUE, m < 300, nrand (2)) ;
1944 cc->SPQR_shrink = 1 ; // restore default shrink = 1 ;
1945
1946 if // (ntol == 0) // old test is fragile ...
1947 (tol == SPQR_DEFAULT_TOL) // use this instead.
1948 {
1949 printf ("using default tol: %g\n", cc->SPQR_tol_used) ;
1950 }
1951
1952 // check norm (A*x-b), x and b sparse
1953 resid = sparse_resid <Entry> (A, anorm, Xsparse, A, cc) ;
1954 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
1955 printf ("Resid1 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
1956
1957 cholmod_l_free_sparse (&Xsparse, cc) ;
1958 cholmod_l_free (n+n, sizeof (Long), Qfill, cc) ;
1959
1960 // -----------------------------------------------------------------
1961 // X = qrsolve (A,B) where X and B are dense, with memory test
1962 // -----------------------------------------------------------------
1963
1964 // use B = dense m-by-2 matrix with some zeros
1965 nb = 5 ;
1966 Bdense = cholmod_l_zeros (m, nb, xtype, cc) ;
1967 B = (Entry *) Bdense->x ;
1968 for (k = 0 ; k < m*nb ; k++)
1969 {
1970 B [k] = (k+1) % 7 ;
1971 }
1972
1973 rank = SPQR_qr <Entry> (
1974 ordering, tol, econ, 2, A,
1975 NULL, Bdense, NULL, &Xdense, NULL, &Qfill, NULL, NULL, NULL,
1976 cc, FALSE, m < 300, nrand (2)) ;
1977
1978 // check norm (A*x-b), x and b dense
1979 resid = dense_resid (A, anorm, Xdense, nb, B, cc) ;
1980 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
1981 printf ("Resid2 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
1982
1983 cholmod_l_free_dense (&Xdense, cc) ;
1984 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
1985
1986 // -----------------------------------------------------------------
1987 // X = qrsolve (A,B) where X and B are full and H is kept
1988 // -----------------------------------------------------------------
1989
1990 cc->SPQR_shrink = 2 ; // shrink = 2 ;
1991 rank = SPQR_qr <Entry> (
1992 ordering, tol, econ, 2, A,
1993 NULL, Bdense, NULL, &Xdense, NULL, &Qfill, &H, &HPinv, &HTau,
1994 cc, FALSE, m < 300, nrand (2)) ;
1995 cc->SPQR_shrink = 1 ; // restore default shrink = 1 ;
1996
1997 cholmod_l_free_dense (&HTau, cc) ;
1998 cholmod_l_free (m, sizeof (Long), HPinv, cc) ;
1999 cholmod_l_free_sparse (&H, cc) ;
2000
2001 // check norm (A*x-b), x and b dense
2002 resid = dense_resid (A, anorm, Xdense, nb, B, cc) ;
2003 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2004 printf ("Resid3 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2005
2006 cholmod_l_free_dense (&Xdense, cc) ;
2007 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2008
2009 // -----------------------------------------------------------------
2010 // [C,R,E] = qr (A,B) where C is sparse and B is full
2011 // -----------------------------------------------------------------
2012
2013 cc->SPQR_shrink = 2 ; // shrink = 2 ;
2014 rank = SPQR_qr <Entry> (
2015 ordering, tol, econ, 0, A,
2016 NULL, Bdense, &Csparse, NULL, &R, &Qfill, NULL, NULL, NULL,
2017 cc, FALSE, m < 300, nrand (2)) ;
2018 cc->SPQR_shrink = 1 ; // restore default shrink = 1 ;
2019
2020 // compute x=R\C and check norm (A*x-b)
2021 Cdense = cholmod_l_sparse_to_dense (Csparse, cc) ;
2022 resid = check_rc (rank, R, A, B, Cdense, nb, anorm, Qfill, cc) ;
2023 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2024 printf ("Resid4 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2025 cholmod_l_free_dense (&Cdense, cc) ;
2026
2027 // check that R'*R = (A*E)'*(A*E)
2028 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2029 printf ("order %d : R'R-(A*E)'*(A*E), Err1: %g\n", ordering, err) ;
2030 maxerr = MAX (maxerr, err) ;
2031
2032 cholmod_l_free_sparse (&Csparse, cc) ;
2033 cholmod_l_free_sparse (&R, cc) ;
2034 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2035
2036 // -----------------------------------------------------------------
2037 // [C,R,E] = qr (A,B) where C and B are full
2038 // -----------------------------------------------------------------
2039
2040 cc->SPQR_shrink = 0 ; // shrink = 0 ;
2041 rank = SPQR_qr <Entry> (
2042 ordering, tol, econ, 0, A,
2043 NULL, Bdense, NULL, &Cdense, &R, &Qfill, NULL, NULL, NULL,
2044 cc, FALSE, m < 300, nrand (2)) ;
2045 cc->SPQR_shrink = 1 ; // restore default shrink = 1 ;
2046
2047 // check that R'*R = (A*E)'*(A*E)
2048 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2049 printf ("order %d : R'R-(A*E)'*(A*E), Err2: %g\n", ordering, err) ;
2050 maxerr = MAX (maxerr, err) ;
2051
2052 cholmod_l_free_dense (&Cdense, cc) ;
2053 cholmod_l_free_sparse (&R, cc) ;
2054 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2055
2056 // -----------------------------------------------------------------
2057 // [C,R,E] = qr (A,B) where C and B are full, simple wrapper
2058 // -----------------------------------------------------------------
2059
2060 SuiteSparseQR <Entry> (ordering, tol, econ, A, Bdense,
2061 &Cdense, &R, &Qfill, cc) ;
2062
2063 // check that R'*R = (A*E)'*(A*E)
2064 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2065 printf ("order %d : R'R-(A*E)'*(A*E), Err3: %g\n", ordering, err) ;
2066 maxerr = MAX (maxerr, err) ;
2067
2068 cholmod_l_free_dense (&Cdense, cc) ;
2069 cholmod_l_free_sparse (&R, cc) ;
2070 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2071
2072 // -----------------------------------------------------------------
2073 // [C,R,E] = qr (A,B) where C and B are sparse, simple wrapper
2074 // -----------------------------------------------------------------
2075
2076 Bsparse = cholmod_l_dense_to_sparse (Bdense, TRUE, cc) ;
2077
2078 SuiteSparseQR <Entry> (ordering, tol, econ, A, Bsparse,
2079 &Csparse, &R, &Qfill, cc) ;
2080
2081 // check that R'*R = (A*E)'*(A*E)
2082 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2083 printf ("order %d : R'R-(A*E)'*(A*E), Err4: %g\n", ordering, err) ;
2084 maxerr = MAX (maxerr, err) ;
2085
2086 cholmod_l_free_sparse (&Csparse, cc) ;
2087 cholmod_l_free_sparse (&Bsparse, cc) ;
2088 cholmod_l_free_sparse (&R, cc) ;
2089 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2090
2091 // -----------------------------------------------------------------
2092 // [CT,R,E] = qr (A,B), but do not return R
2093 // -----------------------------------------------------------------
2094
2095 rank = SPQR_qr <Entry> (
2096 ordering, tol, econ, 1, A,
2097 NULL, Bdense, &Csparse, NULL, NULL, &Qfill, NULL, NULL, NULL,
2098 cc, FALSE, m < 300, nrand (2)) ;
2099
2100 cholmod_l_free_sparse (&Csparse, cc) ;
2101 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2102
2103 // -----------------------------------------------------------------
2104 // [Q,R,E] = qr (A), Q in Householder form
2105 // -----------------------------------------------------------------
2106
2107 rank = SPQR_qr <Entry> (
2108 ordering, tol, econ, -1, A,
2109 NULL, NULL, NULL, NULL, &R, &Qfill, &H, &HPinv, &HTau,
2110 cc, FALSE, m < 300, nrand (2)) ;
2111
2112 // check that R'*R = (A*E)'*(A*E)
2113 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2114 printf ("order %d : R'R-(A*E)'*(A*E), Err5: %g\n", ordering, err) ;
2115 maxerr = MAX (maxerr, err) ;
2116
2117 // solve Ax=b using Householder form
2118 resid = QRsolve <Entry> (A, anorm, rank, 0, H, HTau, HPinv, R,
2119 Qfill, Bdense, cc) ;
2120 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2121 printf ("Resid5 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2122
2123 // solve Ax=b using Q matrix form
2124 resid = QRsolve <Entry> (A, anorm, rank, 1, H, HTau, HPinv, R,
2125 Qfill, Bdense, cc) ;
2126 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2127 printf ("Resid6 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2128
2129 cholmod_l_free_dense (&HTau, cc) ;
2130 cholmod_l_free_sparse (&H, cc) ;
2131 cholmod_l_free (m, sizeof (Long), HPinv, cc) ;
2132 cholmod_l_free (n, sizeof (Long), Qfill, cc) ;
2133 cholmod_l_free_sparse (&R, cc) ;
2134
2135 // -----------------------------------------------------------------
2136 // [Q,R,E] = qr (A), non-economy
2137 // -----------------------------------------------------------------
2138
2139 cc->SPQR_shrink = 0 ; // shrink = 0 ;
2140 I = cholmod_l_speye (m, m, xtype, cc) ;
2141 rank = SPQR_qr <Entry> (
2142 ordering, tol, m, 1, A,
2143 I, NULL, &Q, NULL, &R, &Qfill, NULL, NULL, NULL,
2144 cc, FALSE, m<300, nrand (2)) ;
2145 cc->SPQR_shrink = 1 ; // restore default shrink = 1 ;
2146
2147 // ensure norm (Q*R - A*E) is small
2148 err = check_qr <Entry> (Q, R, A, Qfill, anorm, cc) ;
2149 printf ("order %d : Q*R-A*E Err6: %g\n", ordering, err) ;
2150 maxerr = MAX (maxerr, err) ;
2151
2152 cholmod_l_free_sparse (&I, cc) ;
2153 cholmod_l_free_sparse (&R, cc) ;
2154 cholmod_l_free_sparse (&Q, cc) ;
2155 cholmod_l_free (n+m, sizeof (Long), Qfill, cc) ;
2156
2157 // -----------------------------------------------------------------
2158 // [Q,R,E] = qr (A), non-economy, using simple wrapper
2159 // -----------------------------------------------------------------
2160
2161 if (nrand (2))
2162 {
2163 // use C version
2164 SuiteSparseQR_C_QR (ordering, tol, m, A, &Q, &R, &Qfill, cc) ;
2165 }
2166 else
2167 {
2168 // use C++ version
2169 SuiteSparseQR <Entry> (ordering, tol, m, A, &Q, &R, &Qfill, cc);
2170 }
2171
2172 // ensure norm (Q*R - A*E) is small
2173 err = check_qr <Entry> (Q, R, A, Qfill, anorm, cc) ;
2174 printf ("order %d : Q*R-A*E Err7: %g\n", ordering, err) ;
2175 maxerr = MAX (maxerr, err) ;
2176
2177 cholmod_l_free_sparse (&R, cc) ;
2178 cholmod_l_free_sparse (&Q, cc) ;
2179 cholmod_l_free (n+m, sizeof (Long), Qfill, cc) ;
2180
2181 // -----------------------------------------------------------------
2182 // [R,E] = qr (A)
2183 // -----------------------------------------------------------------
2184
2185 rank = SPQR_qr <Entry> (
2186 ordering, tol, econ, 0, A,
2187 NULL, NULL, NULL, NULL, &R, &Qfill, NULL, NULL, NULL,
2188 cc, FALSE, m < 300, nrand (2)) ;
2189
2190 // check that R'*R = (A*E)'*(A*E)
2191 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2192 printf ("order %d : R'R-(A*E)'*(A*E), Err8: %g\n", ordering, err) ;
2193 maxerr = MAX (maxerr, err) ;
2194 Long rank1 = rank ;
2195
2196 cholmod_l_free_sparse (&R, cc) ;
2197 cholmod_l_free (n, sizeof (Long), Qfill, cc) ;
2198
2199 // -----------------------------------------------------------------
2200 // [R,E] = qr (A) using simple wrapper
2201 // -----------------------------------------------------------------
2202
2203 SuiteSparseQR <Entry> (ordering, tol, econ, A, &R, &Qfill, cc) ;
2204
2205 // check that R'*R = (A*E)'*(A*E)
2206 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2207 printf ("order %d : R'R-(A*E)'*(A*E), Err9: %g\n", ordering, err) ;
2208 maxerr = MAX (maxerr, err) ;
2209
2210 cholmod_l_free_sparse (&R, cc) ;
2211 cholmod_l_free (n, sizeof (Long), Qfill, cc) ;
2212
2213 // -----------------------------------------------------------------
2214 // [ ] = qr (A)
2215 // -----------------------------------------------------------------
2216
2217 // The only thing returned are the statistics (rank, etc)
2218 cc->SPQR_shrink = 0 ; // shrink = 0 ;
2219 rank = SPQR_qr <Entry> (
2220 ordering, tol, econ, 0, A,
2221 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2222 cc, FALSE, m < 300, nrand (2)) ;
2223 cc->SPQR_shrink = 1 ; // restore default shrink = 1 ;
2224
2225 err = (rank != rank1) ;
2226 printf ("order %d : rank %6ld %6ld Err10: %g\n", ordering,
2227 rank, rank1, err) ;
2228 maxerr = MAX (maxerr, err) ;
2229
2230 // -----------------------------------------------------------------
2231 // [C,H,R,E] = qr (A)
2232 // -----------------------------------------------------------------
2233
2234 rank = SPQR_qr <Entry> (
2235 ordering, tol, econ, 0, A,
2236 NULL, Bdense, &Csparse, NULL, &R, &Qfill, &H, &HPinv, &HTau,
2237 cc, FALSE, m < 300, nrand (2)) ;
2238
2239 // compute x=R\C and check norm (A*x-b)
2240 Cdense = cholmod_l_sparse_to_dense (Csparse, cc) ;
2241 resid = check_rc (rank, R, A, B, Cdense, nb, anorm, Qfill, cc) ;
2242 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2243 printf ("Resid7 %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2244 cholmod_l_free_dense (&Cdense, cc) ;
2245
2246 // check that R'*R = (A*E)'*(A*E)
2247 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2248 printf ("order %d : R'R-(A*E)'*(A*E), Err11: %g\n", ordering, err) ;
2249 maxerr = MAX (maxerr, err) ;
2250
2251 cholmod_l_free_sparse (&Csparse, cc) ;
2252 cholmod_l_free_sparse (&R, cc) ;
2253
2254 // compare Q with qmult
2255 err = check_qmult <Entry> (H, HTau, HPinv,
2256 ordering == 2 && /* ntol == 0 */ tol == SPQR_DEFAULT_TOL, cc) ;
2257 printf ("order %d : check qmult Err12: %g\n", ordering, err) ;
2258 maxerr = MAX (maxerr, err) ;
2259
2260 cholmod_l_free_dense (&HTau, cc) ;
2261 cholmod_l_free_sparse (&H, cc) ;
2262 cholmod_l_free (m, sizeof (Long), HPinv, cc) ;
2263 cholmod_l_free (n+nb, sizeof (Long), Qfill, cc) ;
2264 cholmod_l_free_dense (&Bdense, cc) ;
2265
2266 // -----------------------------------------------------------------
2267 // [H,R,E] = qr (A), simple wrapper
2268 // -----------------------------------------------------------------
2269
2270 SuiteSparseQR <Entry> (ordering, tol, econ, A,
2271 &R, &Qfill, &H, &HPinv, &HTau, cc) ;
2272
2273 // check that R'*R = (A*E)'*(A*E)
2274 err = check_r_factor <Entry> (R, A, Qfill, cc) ;
2275 printf ("order %d : R'R-(A*E)'*(A*E), Err13: %g\n", ordering, err) ;
2276 maxerr = MAX (maxerr, err) ;
2277
2278 // compare Q with qmult
2279 err = check_qmult <Entry> (H, HTau, HPinv, FALSE, cc) ;
2280 printf ("order %d : check qmult Err14: %g\n", ordering, err) ;
2281 maxerr = MAX (maxerr, err) ;
2282
2283 cholmod_l_free_sparse (&R, cc) ;
2284 cholmod_l_free_dense (&HTau, cc) ;
2285 cholmod_l_free_sparse (&H, cc) ;
2286 cholmod_l_free (m, sizeof (Long), HPinv, cc) ;
2287 cholmod_l_free (n, sizeof (Long), Qfill, cc) ;
2288
2289 #ifndef NEXPERT
2290
2291 // =================================================================
2292 // === expert routines =============================================
2293 // =================================================================
2294
2295 SuiteSparseQR_factorization <Entry> *QR ;
2296 cholmod_dense *XT, *Zdense, *BT, *Ydense ;
2297 cholmod_sparse *Ysparse ;
2298
2299 // -----------------------------------------------------------------
2300 // QR = qr (A), then solve
2301 // -----------------------------------------------------------------
2302
2303 for (int split = 0 ; split <= 4 ; split++)
2304 {
2305
2306 QR = SPQR_factorize <Entry> (ordering, tol, A, cc,
2307 split, m < 300, nrand (2)) ;
2308
2309 // split == 4 does not use singletons, so it can fail if
2310 // rank < n
2311 int wh = which || (split == 4) ;
2312
2313 // solve Ax=b
2314 nb = 5 ;
2315 Bdense = cholmod_l_zeros (m, nb, xtype, cc) ;
2316 B = (Entry *) Bdense->x ;
2317 for (k = 0 ; k < m*nb ; k++)
2318 {
2319 B [k] = erand (range) ;
2320 }
2321
2322 // Y = Q'*B
2323 Ydense = SPQR_qmult (SPQR_QTX, QR, Bdense, cc,
2324 m < 300, nrand (2)) ;
2325
2326 // X = R\(E*Y)
2327 Xdense = SPQR_solve (SPQR_RETX_EQUALS_B, QR, Ydense, cc,
2328 m < 300, nrand (2)) ;
2329 // check norm (A*x-b), x and b dense
2330 resid = dense_resid (A, anorm, Xdense, nb, B, cc) ;
2331 maxresid [m>n][wh] = MAX (maxresid [m>n][wh], resid) ;
2332 printf ("Resid8_%d %d %ld %d : %g (%d) tol %g\n",
2333 split, m>n, ntol, ordering, resid, wh, tol) ;
2334 cholmod_l_free_dense (&Xdense, cc) ;
2335 cholmod_l_free_dense (&Ydense, cc) ;
2336
2337 // Y = (B'*Q)'
2338 BT = transpose <Entry> (Bdense, cc) ;
2339 XT = SPQR_qmult (SPQR_XQ, QR, BT, cc,
2340 m < 300, nrand (2)) ;
2341
2342 Ydense = transpose <Entry> (XT, cc) ;
2343 cholmod_l_free_dense (&XT, cc) ;
2344 cholmod_l_free_dense (&BT, cc) ;
2345
2346 // X = R\(E*Y)
2347 Xdense = SPQR_solve (SPQR_RETX_EQUALS_B, QR, Ydense, cc,
2348 m < 300, nrand (2)) ;
2349 // check norm (A*x-b), x and b dense
2350 resid = dense_resid (A, anorm, Xdense, nb, B, cc) ;
2351 maxresid [m>n][wh] = MAX (maxresid [m>n][wh], resid) ;
2352 printf ("Resid9_%d %d %ld %d : %g (%d) tol %g\n",
2353 split, m>n, ntol, ordering, resid, wh, tol) ;
2354 cholmod_l_free_dense (&Xdense, cc) ;
2355 cholmod_l_free_dense (&Ydense, cc) ;
2356
2357 // -------------------------------------------------------------
2358 // error testing
2359 // -------------------------------------------------------------
2360
2361 if (ordering == 0 && /* ntol == 0 */ tol == SPQR_DEFAULT_TOL)
2362 {
2363 printf ("Error handling ... expect 3 error messages: \n") ;
2364 err = (SuiteSparseQR_qmult <Entry> (-1, QR, Bdense, cc)
2365 != NULL) ;
2366 cholmod_l_free_dense (&Bdense, cc) ;
2367 Bdense = cholmod_l_zeros (m+1, 1, xtype, cc) ;
2368 err += (SuiteSparseQR_qmult <Entry> (SPQR_QX,QR,Bdense,cc)
2369 != NULL);
2370 cholmod_l_free_dense (&Bdense, cc) ;
2371 Bdense = cholmod_l_zeros (1, m+1, xtype, cc) ;
2372 err += (SuiteSparseQR_qmult <Entry> (SPQR_XQ,QR,Bdense,cc)
2373 != NULL);
2374 if (QR->n1cols > 0)
2375 {
2376 // this will fail; cannot refactorize with singletons
2377 printf ("Error handling ... expect error message:\n") ;
2378 err += (SuiteSparseQR_numeric <Entry> (tol, A, QR, cc)
2379 != FALSE) ;
2380 }
2381 printf ("order %d : error handling Err15: %g\n",
2382 ordering, err) ;
2383 maxerr = MAX (maxerr, err) ;
2384 printf (" ... error handling done\n\n") ;
2385 }
2386
2387 cholmod_l_free_dense (&Bdense, cc) ;
2388
2389 // -------------------------------------------------------------
2390
2391 // solve A'x=b
2392 nb = 5 ;
2393 Bdense = cholmod_l_zeros (n, nb, xtype, cc) ;
2394 B = (Entry *) Bdense->x ;
2395 for (k = 0 ; k < n*nb ; k++)
2396 {
2397 B [k] = erand (range) ;
2398 }
2399 // Y = R'\(E'*B)
2400 Ydense = SPQR_solve (SPQR_RTX_EQUALS_ETB, QR, Bdense, cc,
2401 m < 300, nrand (2)) ;
2402 // X = Q*Y
2403 Xdense = SPQR_qmult (SPQR_QX, QR, Ydense, cc,
2404 m < 300, nrand (2)) ;
2405 // check norm (A'*x-b), x and b dense
2406 resid = dense_resid (AT, anorm, Xdense, nb, B, cc) ;
2407 maxresid [m<n][wh] = MAX (maxresid [m<n][wh], resid) ;
2408 printf ("ResidA_%d %d %ld %d : %g (%d) tol %g\n",
2409 split, m<n, ntol, ordering, resid, wh, tol) ;
2410 cholmod_l_free_dense (&Xdense, cc) ;
2411 cholmod_l_free_dense (&Ydense, cc) ;
2412
2413 // -------------------------------------------------------------
2414 // error testing
2415 // -------------------------------------------------------------
2416
2417 if (!split && ordering == 0 && /* ntol == 0 */
2418 tol == SPQR_DEFAULT_TOL)
2419 {
2420 printf ("Error testing ... expect 3 error messages:\n") ;
2421 err = (SuiteSparseQR_solve <Entry> (-1, QR, Bdense, cc)
2422 != NULL) ;
2423 cholmod_l_free_dense (&Bdense, cc) ;
2424 err += (SuiteSparseQR_solve <Entry> (SPQR_RTX_EQUALS_ETB,
2425 QR, Bdense, cc) != NULL) ;
2426 Bdense = cholmod_l_zeros (n+1, 1, xtype, cc) ;
2427 err += (SuiteSparseQR_solve (SPQR_RTX_EQUALS_ETB,
2428 QR, Bdense, cc) != NULL) ;
2429 printf ("order %d : error handling Err16: %g\n",
2430 ordering, err) ;
2431 maxerr = MAX (maxerr, err) ;
2432 printf (" ... error handling done\n\n") ;
2433 }
2434
2435 SuiteSparseQR_free (&QR, cc) ;
2436 cholmod_l_free_dense (&Bdense, cc) ;
2437 }
2438
2439 // -----------------------------------------------------------------
2440 // QR = qr (A'), then solve
2441 // -----------------------------------------------------------------
2442
2443 // use qmult to solve min-2-norm problem
2444 QR = SuiteSparseQR_factorize <Entry> (ordering, tol, AT, cc) ;
2445
2446 nb = 5 ;
2447 Bdense = cholmod_l_zeros (m, nb, xtype, cc) ;
2448 B = (Entry *) Bdense->x ;
2449 for (k = 0 ; k < m*nb ; k++)
2450 {
2451 B [k] = erand (range) ;
2452 }
2453
2454 // solve X = R'\B
2455 Xdense = SPQR_solve (SPQR_RTX_EQUALS_B, QR, Bdense, cc,
2456 m < 300, nrand (2)) ;
2457 cholmod_l_free_dense (&Xdense, cc) ;
2458
2459 // solve X = R'\(E'*B)
2460 Xdense = SPQR_solve (SPQR_RTX_EQUALS_ETB, QR, Bdense, cc,
2461 m < 300, nrand (2)) ;
2462
2463 // Y = Q*X
2464 Ydense = SPQR_qmult (SPQR_QX, QR, Xdense, cc,
2465 m < 300, nrand (2)) ;
2466
2467 // check norm (A*y-b), y and b dense
2468 resid = dense_resid (A, anorm, Ydense, nb, B, cc) ;
2469 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2470 printf ("ResidB %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2471 cholmod_l_free_dense (&Ydense, cc) ;
2472
2473 // Y = (X'*Q')'
2474 XT = transpose <Entry> (Xdense, cc) ;
2475 Zdense = SPQR_qmult (SPQR_XQT, QR, XT, cc,
2476 m < 300, nrand (2)) ;
2477 Ydense = transpose <Entry> (Zdense, cc) ;
2478 cholmod_l_free_dense (&XT, cc) ;
2479 cholmod_l_free_dense (&Zdense, cc) ;
2480
2481 // check norm (A*y-b), y and b dense
2482 resid = dense_resid (A, anorm, Ydense, nb, B, cc) ;
2483 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2484 printf ("ResidC %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2485 cholmod_l_free_dense (&Ydense, cc) ;
2486 cholmod_l_free_dense (&Xdense, cc) ;
2487
2488 // -----------------------------------------------------------------
2489 // min 2-norm solution using min2norm
2490 // -----------------------------------------------------------------
2491
2492 Xdense = SPQR_min2norm <Entry> (ordering, tol, A, Bdense, cc,
2493 m < 300, nrand (2)) ;
2494
2495 // check norm (A*x-b), y and b dense
2496 resid = dense_resid (A, anorm, Xdense, nb, B, cc) ;
2497 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2498 printf ("ResidD %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2499 cholmod_l_free_dense (&Xdense, cc) ;
2500
2501 cholmod_l_free_dense (&Bdense, cc) ;
2502
2503 // -----------------------------------------------------------------
2504 // sparse case
2505 // -----------------------------------------------------------------
2506
2507 nb = 5 ;
2508 Bdense = cholmod_l_zeros (m, nb, xtype, cc) ;
2509 B = (Entry *) Bdense->x ;
2510 for (k = 0 ; k < m*nb ; k++)
2511 {
2512 B [k] = ((double) (my_rand ( ) % 2)) * erand (range) ;
2513 }
2514 Bsparse = cholmod_l_dense_to_sparse (Bdense, TRUE, cc) ;
2515 cholmod_l_free_dense (&Bdense, cc) ;
2516
2517 // solve X = R'\(E'*B)
2518 Xsparse = NULL ;
2519 Xsparse = SPQR_solve (SPQR_RTX_EQUALS_ETB, QR, Bsparse, cc,
2520 m < 300, nrand (2)) ;
2521
2522 // Y = Q*X
2523 Ysparse = NULL ;
2524 Ysparse = SPQR_qmult (SPQR_QX, QR, Xsparse, cc,
2525 m < 300, nrand (2)) ;
2526
2527 // check norm (A*y-b), y and b sparse
2528 resid = sparse_resid <Entry> (A, anorm, Ysparse, Bsparse, cc) ;
2529 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2530 printf ("ResidE %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2531
2532 cholmod_l_free_sparse (&Xsparse, cc) ;
2533 cholmod_l_free_sparse (&Ysparse, cc) ;
2534
2535 Xsparse = SPQR_min2norm <Entry> (ordering, tol, A, Bsparse, cc,
2536 m < 300, nrand (2)) ;
2537
2538 // check norm (A*x-b), x and b sparse
2539 resid = sparse_resid <Entry> (A, anorm, Xsparse, Bsparse, cc) ;
2540 maxresid [m>n][which] = MAX (maxresid [m>n][which], resid) ;
2541 printf ("ResidF %d %ld %d : %g\n", m>n, ntol, ordering, resid) ;
2542
2543 cholmod_l_free_sparse (&Xsparse, cc) ;
2544 cholmod_l_free_sparse (&Bsparse, cc) ;
2545
2546 SuiteSparseQR_free (&QR, cc) ;
2547 #endif
2548 }
2549 }
2550
2551 // -------------------------------------------------------------------------
2552 // check error handling
2553 // -------------------------------------------------------------------------
2554
2555 printf ("Check error handling, one error message is expected:\n") ;
2556 cholmod_dense *Bgunk = cholmod_l_ones (m+1, 1, xtype, cc) ;
2557 rank = SuiteSparseQR <Entry> (
2558 0, 0, econ, -1, A,
2559 NULL, Bgunk, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
2560 cc) ;
2561 cholmod_l_free_dense (&Bgunk, cc) ;
2562 err = (rank != EMPTY) ;
2563 maxerr = MAX (maxerr, err) ; // rank should be EMPTY
2564 printf (" ... error handling done\n\n") ;
2565
2566 // -------------------------------------------------------------------------
2567 // test non-user callable functions
2568 // -------------------------------------------------------------------------
2569
2570 // attempt to permute A to upper triangular form
2571 Long *Qtrap ;
2572 rank = spqr_trapezoidal (n, Ap, Ai, Ax, 0, NULL, FALSE, &Cp, &Ci, &Cx,
2573 &Qtrap, cc) ;
2574 printf ("Rank of A, if A*P permutable to upper trapezoidal: %ld\n", rank) ;
2575 if (Cp != NULL)
2576 {
2577 nz = Cp [n] ;
2578 cholmod_l_free (n+1, sizeof (Long), Cp, cc) ;
2579 cholmod_l_free (nz, sizeof (Long), Ci, cc) ;
2580 cholmod_l_free (nz, sizeof (Entry), Cx, cc) ;
2581 cholmod_l_free (n, sizeof (Long), Qtrap, cc) ;
2582 }
2583 cholmod_l_free_sparse (&AT, cc) ;
2584
2585 // -------------------------------------------------------------------------
2586 // test the C API
2587 // -------------------------------------------------------------------------
2588
2589 qrtest_C (A, anorm, errs, maxresid, cc) ;
2590
2591 // -------------------------------------------------------------------------
2592 // final results
2593 // -------------------------------------------------------------------------
2594
2595 errs [0] = CHECK_NAN (maxerr) ;
2596 errs [1] = CHECK_NAN (maxresid [0][0]) ;
2597 errs [2] = CHECK_NAN (maxresid [0][1]) ;
2598 errs [3] = CHECK_NAN (maxresid [1][0]) ;
2599 errs [4] = CHECK_NAN (maxresid [1][1]) ;
2600 }
2601
2602
2603 // =============================================================================
2604 // === do_matrix ===============================================================
2605 // =============================================================================
2606
2607 // Read in a matrix, and use it to test SuiteSparseQR
2608 // If kind == 0, then the first two residuals should be low.
2609
2610 int do_matrix2 (int kind, cholmod_sparse *A, cholmod_common *cc) ;
2611
do_matrix(int kind,FILE * file,cholmod_common * cc)2612 int do_matrix (int kind, FILE *file, cholmod_common *cc)
2613 {
2614 cholmod_sparse *A ;
2615
2616 int nfail0 = 0 ;
2617 int nfail1 = 0 ;
2618 int nfail2 = 0 ;
2619 int nfail3 = 0 ;
2620
2621 // -------------------------------------------------------------------------
2622 // read in the matrix
2623 // -------------------------------------------------------------------------
2624
2625 A = cholmod_l_read_sparse (file, cc) ;
2626 if (A == NULL)
2627 {
2628 fprintf (stderr, "Unable to read matrix\n") ;
2629 return (1) ;
2630 }
2631 Long m = A->nrow ;
2632 Long n = A->ncol ;
2633 fprintf (stderr, "%5ld by %5ld : ", m, n) ;
2634 if (sizeof (Long) > sizeof (int) && (m > 10000 || n > 10000))
2635 {
2636 fprintf (stderr, "(test skipped on 64-bit systems)\n") ;
2637 cholmod_l_free_sparse (&A, cc) ;
2638 return (0) ;
2639 }
2640
2641 // defaults
2642 cc->SPQR_grain = 1 ; // no parallel analysis
2643 printf ("\nBeginning CPU tests [\n") ;
2644 fprintf (stderr, " CPU ") ;
2645 nfail0 = do_matrix2 (kind, A, cc) ;
2646
2647 // non-defaults to test TBB, if installed (will not use the GPU)
2648 cc->SPQR_grain = 4 ; // grain size relative to total work
2649 nfail2 = do_matrix2 (kind, A, cc) ;
2650 cc->SPQR_grain = 1 ; // no parallel analysis
2651 printf ("\nCPU tests done ]\n") ;
2652
2653 // test the GPU, if installed
2654 #ifdef GPU_BLAS
2655 cc->useGPU = TRUE ;
2656 // was 3.5 * ((size_t) 1024 * 1024 * 1024) ;
2657 size_t totmem, availmem ;
2658 double t = SuiteSparse_time ( ) ;
2659 cholmod_l_gpu_memorysize (&totmem, &availmem, cc) ;
2660 t = SuiteSparse_time ( ) - t ;
2661 cc->gpuMemorySize = availmem ;
2662 printf ("\nBeginning GPU tests, GPU memory %g MB warmup time %g[\n",
2663 (double) (cc->gpuMemorySize) / (1024*1024), t) ;
2664 fprintf (stderr, " GPU ") ;
2665 nfail1 = do_matrix2 (kind, A, cc) ;
2666 printf ("\nGPU tests done ]\n") ;
2667 if (m > 200)
2668 {
2669 // try with a tiny GPU memory size, but only for a few matrices
2670 // in the test set. Each front will go in its own stage.
2671 printf ("\nBeginning GPU tests with tiny GPU memory [\n") ;
2672 cc->gpuMemorySize = 0 ;
2673 nfail3 = do_matrix2 (kind, A, cc) ;
2674 // restore defaults
2675 cc->useGPU = FALSE ;
2676 printf ("\nGPU tests done (tiny memory) ]\n") ;
2677 }
2678 #endif
2679
2680 cholmod_l_free_sparse (&A, cc) ;
2681
2682 printf ("\n") ;
2683 fprintf (stderr, "\n") ;
2684 return (nfail0 + nfail1 + nfail2 + nfail3) ;
2685 }
2686
2687
2688
do_matrix2(int kind,cholmod_sparse * A,cholmod_common * cc)2689 int do_matrix2 (int kind, cholmod_sparse *A, cholmod_common *cc)
2690 {
2691 double errs [5] = {0,0,0,0,0} ;
2692 Long m = A->nrow ;
2693 Long n = A->ncol ;
2694
2695 // -------------------------------------------------------------------------
2696 // use it to test SuiteSparseQR
2697 // -------------------------------------------------------------------------
2698
2699 if (A->xtype == CHOLMOD_COMPLEX && A->stype == 0)
2700 {
2701 qrtest <Complex> (A, errs, cc) ;
2702 }
2703 else if (A->xtype == CHOLMOD_REAL)
2704 {
2705 if (A->stype != 0)
2706 {
2707 cholmod_sparse *A1 ;
2708 A1 = cholmod_l_copy (A, 0, 1, cc) ;
2709 qrtest <double> (A1, errs, cc) ;
2710 cholmod_l_free_sparse (&A1, cc) ;
2711 }
2712 else
2713 {
2714 qrtest <double> (A, errs, cc) ;
2715 }
2716 }
2717 else
2718 {
2719 // cannot handle ZOMPLEX, PATTERN, or symmetric/Hermitian COMPLEX
2720 fprintf (stderr, "invalid matrix\n") ;
2721 errs [0] = 1 ;
2722 }
2723
2724 // -------------------------------------------------------------------------
2725 // report the results
2726 // -------------------------------------------------------------------------
2727
2728 if (kind == 0)
2729 {
2730 printf ("First Resid and ") ;
2731 }
2732 printf ("Err should be low:\n") ;
2733 printf ("RESULT: Err %8.1e Resid %8.1e %8.1e", errs [0],
2734 errs [1], errs [2]) ;
2735 if (m == n)
2736 {
2737 printf (" ") ;
2738 }
2739 else
2740 {
2741 printf (" %8.1e %8.1e", errs [3], errs [4]) ;
2742 }
2743
2744 if (errs [0] > 1e-10)
2745 {
2746 printf (" : FAIL\n") ;
2747 fprintf (stderr, "Error: %g FAIL\n", errs [0]) ;
2748 return (1) ;
2749 }
2750
2751 // if kind == 0, then this full-rank matrix should have low residual
2752 if (kind == 0 && (errs [1] > 1e-10))
2753 {
2754 printf (" : FAIL\n") ;
2755 fprintf (stderr, "error: %g FAIL\n", errs [1]) ;
2756 return (1) ;
2757 }
2758
2759 printf (" : OK.") ;
2760 fprintf (stderr, "OK.") ;
2761 return (0) ;
2762 }
2763
2764
2765 // =============================================================================
2766 // === qrtest main =============================================================
2767 // =============================================================================
2768
2769 #define LEN 200
2770
main(int argc,char ** argv)2771 int main (int argc, char **argv)
2772 {
2773 cholmod_common Common, *cc ;
2774 char matrix_name [LEN+1] ;
2775 int kind, nfail = 0 ;
2776
2777 // -------------------------------------------------------------------------
2778 // start CHOLMOD
2779 // -------------------------------------------------------------------------
2780
2781 cc = &Common ;
2782 cholmod_l_start (cc) ;
2783 normal_memory_handler (cc) ;
2784
2785 if (argc == 1)
2786 {
2787
2788 // ---------------------------------------------------------------------
2789 // Usage: qrtest < input.mtx
2790 // ---------------------------------------------------------------------
2791
2792 nfail += do_matrix (1, stdin, cc) ;
2793 }
2794 else
2795 {
2796
2797 // ---------------------------------------------------------------------
2798 // Usage: qrtest matrixlist
2799 // ---------------------------------------------------------------------
2800
2801 // Each line of the matrixlist file contains an integer indicating if
2802 // the residuals should all be low (0=lo, 1=can be high), and a file
2803 // name containing the matrix in Matrix Market format.
2804
2805 FILE *file = fopen (argv [1], "r") ;
2806 if (file == NULL)
2807 {
2808 fprintf (stderr, "Unable to open %s\n", argv [1]) ;
2809 exit (1) ;
2810 }
2811
2812 while (1)
2813 {
2814 if (fscanf (file, "%d %100s\n", &kind, matrix_name) != 2)
2815 {
2816 break ;
2817 }
2818 fprintf (stderr, "%-30s ", matrix_name) ;
2819 FILE *matrix = fopen (matrix_name, "r") ;
2820 if (matrix == NULL)
2821 {
2822 fprintf (stderr, "Unable to open %s\n", matrix_name) ;
2823 nfail++ ;
2824 }
2825 nfail += do_matrix (kind, matrix, cc) ;
2826
2827 fclose (matrix) ;
2828 }
2829 fclose (file) ;
2830 }
2831
2832 // -------------------------------------------------------------------------
2833 // report the results
2834 // -------------------------------------------------------------------------
2835
2836 cholmod_l_finish (cc) ;
2837
2838 if (cc->malloc_count != 0)
2839 {
2840 nfail++ ;
2841 fprintf (stderr, "memory leak: %ld objects\n", (Long) cc->malloc_count);
2842 }
2843 if (cc->memory_inuse != 0)
2844 {
2845 nfail++ ;
2846 fprintf (stderr, "memory leak: %ld bytes\n", (Long) cc->memory_inuse) ;
2847 }
2848
2849 if (nfail == 0)
2850 {
2851 fprintf (stderr, "\nAll tests passed\n") ;
2852 }
2853 else
2854 {
2855 fprintf (stderr, "\nTest FAILURES: %d\n", nfail) ;
2856 }
2857
2858 return (0) ;
2859 }
2860