1 // Copyright (c) 2015-2016, Massachusetts Institute of Technology
2 // Copyright (c) 2016-2017 Sandia Corporation
3 // Copyright (c) 2017 NTESS, LLC.
4
5 // This file is part of the Compressed Continuous Computation (C3) Library
6 // Author: Alex A. Gorodetsky
7 // Contact: alex@alexgorodetsky.com
8
9 // All rights reserved.
10
11 // Redistribution and use in source and binary forms, with or without modification,
12 // are permitted provided that the following conditions are met:
13
14 // 1. Redistributions of source code must retain the above copyright notice,
15 // this list of conditions and the following disclaimer.
16
17 // 2. Redistributions in binary form must reproduce the above copyright notice,
18 // this list of conditions and the following disclaimer in the documentation
19 // and/or other materials provided with the distribution.
20
21 // 3. Neither the name of the copyright holder nor the names of its contributors
22 // may be used to endorse or promote products derived from this software
23 // without specific prior written permission.
24
25 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
28 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
29 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
31 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
33 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35
36 //Code
37
38
39
40
41
42 /** \file quasimatrix.c
43 * Provides algorithms for quasimatrix manipulation
44 */
45
46 #include <stdlib.h>
47 #include <assert.h>
48 #include <math.h>
49 #include <string.h>
50
51 #include "stringmanip.h"
52 #include "array.h"
53 #include "linalg.h"
54
55 #include "quasimatrix.h"
56
57 #define ZEROTHRESH 1e2*DBL_EPSILON
58
59 /** \struct Quasimatrix
60 * \brief Defines a vector-valued function
61 * \var Quasimatrix::n
62 * number of functions
63 * \var Quasimatrix::funcs
64 * array of functions
65 */
66 struct Quasimatrix {
67 size_t n;
68 struct GenericFunction ** funcs;
69 };
70
71 /*********************************************************//**
72 Allocate space for a quasimatrix
73
74 \param[in] n - number of columns of quasimatrix
75
76 \return quasimatrix
77 *************************************************************/
78 struct Quasimatrix *
quasimatrix_alloc(size_t n)79 quasimatrix_alloc(size_t n){
80
81 struct Quasimatrix * qm;
82 if ( NULL == (qm = malloc(sizeof(struct Quasimatrix)))){
83 fprintf(stderr, "failed to allocate memory for quasimatrix.\n");
84 exit(1);
85 }
86 qm->n = n;
87 if ( NULL == (qm->funcs = malloc(n * sizeof(struct GenericFunction *)))){
88 fprintf(stderr, "failed to allocate memory for quasimatrix.\n");
89 exit(1);
90 }
91 size_t ii;
92 for (ii = 0; ii < n; ii++){
93 qm->funcs[ii] = NULL;
94 }
95 return qm;
96 }
97
98 /*********************************************************//**
99 Free functions
100 *************************************************************/
quasimatrix_free_funcs(struct Quasimatrix * qm)101 void quasimatrix_free_funcs(struct Quasimatrix * qm)
102 {
103 assert (qm != NULL);
104 if (qm->funcs != NULL){
105 for (size_t ii = 0; ii < qm->n ;ii++){
106 generic_function_free(qm->funcs[ii]); qm->funcs[ii] = NULL;
107 }
108 free(qm->funcs); qm->funcs = NULL;
109 }
110 }
111
112 /*********************************************************//**
113 Free memory allocated to quasimatrix
114
115 \param[in,out] qm
116 *************************************************************/
quasimatrix_free(struct Quasimatrix * qm)117 void quasimatrix_free(struct Quasimatrix * qm){
118
119 if (qm != NULL){
120 quasimatrix_free_funcs(qm);
121 free(qm);qm=NULL;
122 }
123 }
124
125 /*********************************************************//**
126 Get size
127 *************************************************************/
quasimatrix_get_size(const struct Quasimatrix * q)128 size_t quasimatrix_get_size(const struct Quasimatrix * q)
129 {
130 assert(q != NULL);
131 return q->n;
132 }
133
134 /*********************************************************//**
135 Set size
136 *************************************************************/
quasimatrix_set_size(struct Quasimatrix * q,size_t n)137 void quasimatrix_set_size(struct Quasimatrix * q,size_t n)
138 {
139 assert(q != NULL);
140 q->n = n;
141 }
142
143 /*********************************************************//**
144 Get function
145 *************************************************************/
146 struct GenericFunction *
quasimatrix_get_func(const struct Quasimatrix * q,size_t ind)147 quasimatrix_get_func(const struct Quasimatrix * q, size_t ind)
148 {
149 assert(q != NULL);
150 assert(ind < q->n);
151 return q->funcs[ind];
152 }
153
154 /*********************************************************//**
155 set function by copying
156 *************************************************************/
157 void
quasimatrix_set_func(struct Quasimatrix * q,const struct GenericFunction * gf,size_t ind)158 quasimatrix_set_func(struct Quasimatrix * q, const struct GenericFunction * gf,
159 size_t ind)
160 {
161 assert(q != NULL);
162 assert(ind < q->n);
163 generic_function_free(q->funcs[ind]);
164 q->funcs[ind] = generic_function_copy(gf);
165 }
166
167 /*********************************************************//**
168 Get all functions
169 *************************************************************/
170 struct GenericFunction **
quasimatrix_get_funcs(const struct Quasimatrix * q)171 quasimatrix_get_funcs(const struct Quasimatrix * q)
172 {
173 assert(q != NULL);
174 return q->funcs;
175 }
176
177 /*********************************************************//**
178 Set all functions
179 *************************************************************/
180 void
quasimatrix_set_funcs(struct Quasimatrix * q,struct GenericFunction ** gf)181 quasimatrix_set_funcs(struct Quasimatrix * q, struct GenericFunction ** gf)
182 {
183 assert(q != NULL);
184 quasimatrix_free_funcs(q);
185 q->funcs = gf;
186 }
187
188 /*********************************************************//**
189 Get reference to all functions
190 *************************************************************/
191 void
quasimatrix_get_funcs_ref(const struct Quasimatrix * q,struct GenericFunction *** gf)192 quasimatrix_get_funcs_ref(const struct Quasimatrix * q,struct GenericFunction *** gf)
193 {
194 assert(q != NULL);
195 *gf = q->funcs;
196 }
197
198 /*********************************************************//**
199 Create a quasimatrix by approximating 1d functions
200
201 \param[in] n - number of columns of quasimatrix
202 \param[in,out] fw - wrapped functions
203 \param[in] fc - function class of each column
204 \param[in] aopts - approximation options
205
206 \return quasimatrix
207
208 // same approximation arguments in each dimension
209 *************************************************************/
210 struct Quasimatrix *
quasimatrix_approx1d(size_t n,struct Fwrap * fw,enum function_class * fc,void * aopts)211 quasimatrix_approx1d(size_t n, struct Fwrap * fw,
212 enum function_class * fc,
213 void * aopts)
214
215 {
216 struct Quasimatrix * qm = quasimatrix_alloc(n);
217 size_t ii;
218 for (ii = 0; ii < n; ii++){
219 /* printf("ii=%zu\n",ii); */
220 fwrap_set_which_eval(fw,ii);
221 qm->funcs[ii] = generic_function_approximate1d(fc[ii],aopts,fw);
222 /* printf("integral = %G\n",generic_function_integral(qm->funcs[ii])); */
223 }
224 return qm;
225 }
226
227 /*********************************************************
228 Create a quasimatrix from a fiber_cuts array
229
230 \param[in] n - number of columns of quasimatrix
231 \param[in] f - function
232 \param[in] fcut - array of fiber cuts
233 \param[in] fc - function class of each column
234 \param[in] sub_type - sub_type of each column
235 \param[in] lb - lower bound of inputs to functions
236 \param[in] ub - upper bound of inputs to functions
237 \param[in] aopts - approximation options
238
239 \return quasimatrix
240 *************************************************************/
241 /* struct Quasimatrix * */
242 /* quasimatrix_approx_from_fiber_cuts(size_t n, */
243 /* double (*f)(double,void *), */
244 /* struct FiberCut ** fcut, */
245 /* enum function_class fc, */
246 /* void * sub_type,double lb, */
247 /* double ub, void * aopts) */
248 /* { */
249 /* struct Quasimatrix * qm = quasimatrix_alloc(n); */
250 /* size_t ii; */
251 /* for (ii = 0; ii < n; ii++){ */
252 /* qm->funcs[ii] = */
253 /* generic_function_approximate1d(f, fcut[ii], */
254 /* fc, sub_type, */
255 /* lb, ub, aopts); */
256 /* } */
257 /* return qm; */
258 /* } */
259
260 /*********************************************************//**
261 Copy a quasimatrix
262
263 \param[in] qm - quasimatrix to copy
264
265 \return copied quasimatrix
266 *************************************************************/
267 struct Quasimatrix *
quasimatrix_copy(const struct Quasimatrix * qm)268 quasimatrix_copy(const struct Quasimatrix * qm)
269 {
270 struct Quasimatrix * qmo = quasimatrix_alloc(qm->n);
271 size_t ii;
272 for (ii = 0; ii < qm->n; ii++){
273 qmo->funcs[ii] = generic_function_copy(qm->funcs[ii]);
274 }
275
276 return qmo;
277 }
278
279 /*********************************************************//**
280 Serialize a quasimatrix
281
282 \param[in,out] ser - stream to serialize to
283 \param[in] qm - quasimatrix
284 \param[in,out] totSizeIn - if NULL then serialize,
285 if not NULL then return size;
286
287 \return ptr - ser shifted by number of bytes
288 *************************************************************/
289 unsigned char *
quasimatrix_serialize(unsigned char * ser,const struct Quasimatrix * qm,size_t * totSizeIn)290 quasimatrix_serialize(unsigned char * ser,
291 const struct Quasimatrix * qm,
292 size_t *totSizeIn)
293 {
294 // n -> func -> func-> ... -> func
295 if (totSizeIn != NULL){
296 size_t ii;
297 size_t totSize = sizeof(size_t);
298 for (ii = 0; ii < qm->n; ii++){
299 size_t size_temp = 0 ;
300 serialize_generic_function(NULL,qm->funcs[ii],&size_temp);
301 totSize += size_temp;
302
303 }
304 *totSizeIn = totSize;
305 return ser;
306 }
307
308 unsigned char * ptr = ser;
309 ptr = serialize_size_t(ptr, qm->n);
310 for (size_t ii = 0; ii < qm->n; ii++){
311 ptr = serialize_generic_function(ptr, qm->funcs[ii],NULL);
312 }
313 return ptr;
314 }
315
316 /*********************************************************//**
317 Deserialize a quasimatrix
318
319 \param[in] ser - serialized quasimatrix
320 \param[in,out] qm - quasimatrix
321
322 \return shifted ser after deserialization
323 *************************************************************/
324 unsigned char *
quasimatrix_deserialize(unsigned char * ser,struct Quasimatrix ** qm)325 quasimatrix_deserialize(unsigned char * ser,
326 struct Quasimatrix ** qm)
327 {
328 unsigned char * ptr = ser;
329
330 size_t n;
331 ptr = deserialize_size_t(ptr, &n);
332 *qm = quasimatrix_alloc(n);
333
334 size_t ii;
335 for (ii = 0; ii < n; ii++){
336 ptr = deserialize_generic_function(ptr,
337 &((*qm)->funcs[ii]));
338 }
339
340 return ptr;
341 }
342
343 /*********************************************************//**
344 Generate a quasimatrix with orthonormal columns
345
346 \param[in] n - number of columns
347 \param[in] fc - function class
348 \param[in] opts - options
349
350
351 \return quasimatrix with orthonormal columns
352 *************************************************************/
353 struct Quasimatrix *
quasimatrix_orth1d(size_t n,enum function_class fc,void * opts)354 quasimatrix_orth1d(size_t n, enum function_class fc,
355 void * opts)
356 {
357 struct Quasimatrix * qm = quasimatrix_alloc(n);
358 generic_function_array_orth(n,qm->funcs,fc,opts);
359 return qm;
360 }
361
362 /*********************************************************//**
363 Find the absolute maximum element of a
364 quasimatrix of 1d functions
365
366 \param[in] qm - quasimatrix
367 \param[in,out] absloc - location (row) of maximum
368 \param[in,out] absval - value of maximum
369 \param[in] optargs - optimization arguments
370
371 \return col - column of maximum element
372 *************************************************************/
373 size_t
quasimatrix_absmax(struct Quasimatrix * qm,double * absloc,double * absval,void * optargs)374 quasimatrix_absmax(struct Quasimatrix * qm,
375 double * absloc, double * absval,
376 void * optargs)
377 {
378 size_t col = 0;
379 size_t ii;
380 double temp_loc;
381 double temp_max;
382 *absval = generic_function_absmax(qm->funcs[0],absloc,
383 optargs);
384 for (ii = 1; ii < qm->n; ii++){
385 temp_max = generic_function_absmax(qm->funcs[ii],
386 &temp_loc,optargs);
387 if (temp_max > *absval){
388 col = ii;
389 *absval = temp_max;
390 *absloc = temp_loc;
391 }
392 }
393 return col;
394 }
395
396
397
398 ///////////////////////////////////////////
399 // Linear Algebra
400 ///////////////////////////////////////////
401
402 /*********************************************************//**
403 Inner product of integral of quasimatrices
404 returns sum_i=1^n int A->funcs[ii], B->funcs[ii] dx
405
406 \param[in] A - quasimatrix
407 \param[in] B - quasimatrix
408
409 \return mag : inner product
410 *************************************************************/
quasimatrix_inner(const struct Quasimatrix * A,const struct Quasimatrix * B)411 double quasimatrix_inner(const struct Quasimatrix * A,
412 const struct Quasimatrix * B)
413 {
414 assert (A != NULL);
415 assert (B != NULL);
416 assert(A->n == B->n);
417 assert (A->funcs != NULL);
418 assert (B->funcs != NULL);
419
420 size_t ii;
421 double int1;
422 double mag = 0.0;
423 //printf("here! %zu,%zu\n",A1->n,A2->n);
424 for (ii = 0; ii < A->n; ii++){
425 int1 = generic_function_inner(A->funcs[ii],B->funcs[ii]);
426 mag += int1;
427 }
428 //printf("mag = %3.2f \n", mag);
429
430 return mag;
431 }
432
433 /*********************************************************//**
434 Quasimatrix - vector multiplication
435
436 \param[in] Q - quasimatrix
437 \param[in] v - array
438
439 \return f - generic function
440 *************************************************************/
441 struct GenericFunction *
qmv(const struct Quasimatrix * Q,const double * v)442 qmv(const struct Quasimatrix * Q, const double * v)
443 {
444 struct GenericFunction * f =
445 generic_function_lin_comb(Q->n,Q->funcs,v);
446 return f;
447 }
448
449 /*********************************************************//**
450 Quasimatrix - matrix multiplication
451
452 \param[in] Q - quasimatrix
453 \param[in] R - matrix (fortran order)
454 \param[in] b - number of columns of R
455
456 \return quasimatrix
457 *************************************************************/
458 struct Quasimatrix *
qmm(const struct Quasimatrix * Q,const double * R,size_t b)459 qmm(const struct Quasimatrix * Q, const double * R, size_t b)
460 {
461 struct Quasimatrix * B = quasimatrix_alloc(b);
462 size_t ii;
463 for (ii = 0; ii < b; ii++){
464 B->funcs[ii] =
465 generic_function_lin_comb(Q->n,Q->funcs,
466 R + ii*Q->n);
467 }
468 return B;
469 }
470
471 /*********************************************************//**
472 Quasimatrix - transpose matrix multiplication
473
474 \param[in] Q - quasimatrix
475 \param[in,out] R - matrix (fortran order)
476 \param[in] b - number of rows of R
477
478 \return quasimatrix
479 *************************************************************/
480 struct Quasimatrix *
qmmt(const struct Quasimatrix * Q,const double * R,size_t b)481 qmmt(const struct Quasimatrix * Q, const double * R, size_t b)
482 {
483 double * Rt = calloc_double(Q->n * b);
484 size_t ii, jj;
485 for (ii = 0; ii < b; ii++){
486 for (jj = 0; jj < Q->n; jj++){
487 Rt[ii * Q->n + jj] = R[jj * b + ii];
488 }
489 }
490 struct Quasimatrix * B = qmm(Q,Rt, b);
491 free(Rt);
492 return B;
493 }
494
495 /*********************************************************//**
496 Compute ax + by where x, y are quasimatrices and a,b are scalars
497
498 \param[in] a - scale for x
499 \param[in] x - quasimatrix
500 \param[in] b - scale for y
501 \param[in] y - quasimatrix
502
503 \return quasimatrix result
504 *************************************************************/
505 struct Quasimatrix *
quasimatrix_daxpby(double a,const struct Quasimatrix * x,double b,const struct Quasimatrix * y)506 quasimatrix_daxpby(double a, const struct Quasimatrix * x,
507 double b, const struct Quasimatrix * y)
508 {
509 struct Quasimatrix * qm = NULL;
510 if ((x == NULL) && (y == NULL)){
511 return qm;
512 }
513 else if ((x == NULL) && (y != NULL)){
514 //printf("here y not null \n");
515 qm = quasimatrix_alloc(y->n);
516 free(qm->funcs); qm->funcs = NULL;
517 qm->funcs = generic_function_array_daxpby(y->n, b, 1, y->funcs, 0.0,1,NULL);
518 }
519 else if ((x != NULL) && (y == NULL)){
520 //printf("here x not null \n");
521 qm = quasimatrix_alloc(x->n);
522 free(qm->funcs); qm->funcs = NULL;
523 qm->funcs = generic_function_array_daxpby(x->n, a, 1, x->funcs, 0.0,1,NULL);
524 //printf("out of x not null \n");
525 }
526 else{
527 //printf("here in qm daxpby\n");
528 qm = quasimatrix_alloc(x->n);
529 free(qm->funcs); qm->funcs = NULL;
530 qm->funcs = generic_function_array_daxpby(x->n,a,1,x->funcs,b,1,y->funcs);
531 }
532
533 return qm;
534 }
535
536
537 /*********************************************************//**
538 Compute the householder triangularization of a
539 quasimatrix. (Trefethan 2010) whose columns consist of
540 one dimensional functions
541
542 \param[in,out] A - quasimatrix to triangularize
543 \param[in,out] R - upper triangluar matrix
544 \param[in] opts - options for approximation
545
546 \return quasimatrix denoting the Q term
547
548 \note
549 For now I have only implemented this for polynomial
550 function class and legendre subtype
551 *************************************************************/
552 struct Quasimatrix *
quasimatrix_householder_simple(struct Quasimatrix * A,double * R,void * opts)553 quasimatrix_householder_simple(struct Quasimatrix * A,
554 double * R, void * opts)
555 {
556
557 size_t ncols = A->n;
558
559 // generate two quasimatrices needed for householder
560 enum function_class fc = generic_function_get_fc(A->funcs[0]);
561 struct Quasimatrix * Q = quasimatrix_orth1d(ncols,fc,opts);
562 struct Quasimatrix * V = quasimatrix_alloc(ncols);
563
564 int out = 0;
565 out = quasimatrix_householder(A,Q,V,R);
566
567 assert(out == 0);
568 out = quasimatrix_qhouse(Q,V);
569 assert(out == 0);
570
571 quasimatrix_free(V);
572 return Q;
573 }
574
575
576 /*********************************************************//**
577 Compute the householder triangularization of a quasimatrix. (Trefethan 2010)
578
579 \param[in,out] A - quasimatrix to triangularize(destroyed)
580 \param[in,out] E - quasimatrix with orthonormal columns
581 \param[in,out] V - allocated space for a quasimatrix,
582 stores reflectors in the end
583 \param[in,out] R - allocated space upper triangular factor
584
585 \return info (if != 0 then something is wrong)
586 *************************************************************/
587 int
quasimatrix_householder(struct Quasimatrix * A,struct Quasimatrix * E,struct Quasimatrix * V,double * R)588 quasimatrix_householder(struct Quasimatrix * A,
589 struct Quasimatrix * E,
590 struct Quasimatrix * V, double * R)
591 {
592 size_t ii, jj;
593 struct GenericFunction * e;
594 struct GenericFunction * x;
595 struct GenericFunction * v;
596 struct GenericFunction * v2;
597 struct GenericFunction * atemp;
598 double rho, sigma, alpha;
599 double temp1;
600 for (ii = 0; ii < A->n; ii++){
601 /* printf("ii = %zu\n",ii); */
602 e = E->funcs[ii];
603 x = A->funcs[ii];
604 rho = generic_function_norm(x);
605
606 R[ii * A->n + ii] = rho;
607
608 alpha = generic_function_inner(e,x);
609
610 if (alpha >= ZEROTHRESH){
611 generic_function_flip_sign(e);
612 }
613
614 /* printf("compute v, rho = %G\n",rho); */
615 /* printf("integral of x = %G\n",generic_function_integral(x)); */
616 /* printf("norm of e = %G\n",generic_function_norm(e)); */
617 v = generic_function_daxpby(rho,e,-1.0,x);
618 /* printf("got v\n"); */
619 // skip step improve orthogonality
620 // improve orthogonality
621
622 sigma = generic_function_norm(v);
623
624 if (fabs(sigma) <= ZEROTHRESH){
625 V->funcs[ii] = generic_function_copy(e);
626 generic_function_free(v);
627 }
628 else {
629 V->funcs[ii] = generic_function_daxpby(1.0/sigma, v, 0.0, NULL);
630 generic_function_free(v);
631 }
632 v2 = V->funcs[ii];
633
634 for (jj = ii+1; jj < A->n; jj++){
635 /* printf("\t jj = %zu\n",jj); */
636 temp1 = generic_function_inner(v2,A->funcs[jj]);
637 if (fabs(temp1) < ZEROTHRESH){
638 temp1 = 0.0;
639 }
640
641 atemp = generic_function_daxpby(1.0,
642 A->funcs[jj],
643 -2.0 * temp1, v2);
644 R[jj * A->n + ii] = generic_function_inner(e,
645 atemp);
646
647 generic_function_free(A->funcs[jj]);
648
649 A->funcs[jj] =
650 generic_function_daxpby(1.0, atemp,
651 -R[jj * A->n + ii],e);
652 generic_function_free(atemp);
653 }
654
655 }
656 return 0;
657 }
658
659 /*********************************************************//**
660 Compute the Q matrix from householder reflectors (Trefethan 2010)
661
662 \param[in,out] Q - quasimatrix E obtained after
663 househodler_qm (destroyed
664 \param[in,out] V - Householder functions,
665 obtained from quasimatrix_householder
666
667 \return info (if != 0 then something is wrong)
668 *************************************************************/
quasimatrix_qhouse(struct Quasimatrix * Q,struct Quasimatrix * V)669 int quasimatrix_qhouse(struct Quasimatrix * Q,
670 struct Quasimatrix * V)
671 {
672
673 int info = 0;
674 size_t ii, jj;
675
676
677
678 struct GenericFunction * v;
679 struct GenericFunction * q;
680 double temp1;
681 size_t counter = 0;
682 ii = Q->n-1;
683 while (counter < Q->n){
684 v = V->funcs[ii];
685 for (jj = ii; jj < Q->n; jj++){
686 temp1 = generic_function_inner(v,Q->funcs[jj]);
687 q = generic_function_daxpby(1.0, Q->funcs[jj],
688 -2.0 * temp1, v);
689
690 generic_function_free(Q->funcs[jj]);
691 Q->funcs[jj] = generic_function_copy(q);
692 generic_function_free(q);
693 }
694 ii = ii - 1;
695 counter = counter + 1;
696 }
697
698 return info;
699 }
700
701 /*********************************************************//**
702 Compute the LU decomposition of a quasimatrix of one
703 dimensional functions (Townsend 2015)
704
705 \param[in] A - quasimatrix to decompose
706 \param[in,out] L - quasimatrix representing L factor
707 \param[in,out] u - allocated space for U factor
708 \param[in,out] p - pivots
709 \param[in] approxargs - approximation arguments for each column
710 \param[in] optargs - optimization arguments
711
712 \return inno
713
714 \note
715 info =
716 - 0 converges
717 - <0 low rank ( rank = A->n + info )
718 *************************************************************/
quasimatrix_lu1d(struct Quasimatrix * A,struct Quasimatrix * L,double * u,double * p,void * approxargs,void * optargs)719 int quasimatrix_lu1d(struct Quasimatrix * A,
720 struct Quasimatrix * L, double * u,
721 double * p, void * approxargs,
722 void * optargs)
723 {
724 int info = 0;
725
726 size_t ii,kk;
727 double val, amloc;
728 struct GenericFunction * temp;
729
730 for (kk = 0; kk < A->n; kk++){
731
732 generic_function_absmax(A->funcs[kk], &amloc,optargs);
733 p[kk] = amloc;
734
735 val = generic_function_1d_eval(A->funcs[kk], amloc);
736
737 if (fabs(val) < 2.0 * ZEROTHRESH){
738 L->funcs[kk] =
739 generic_function_constant(1.0,POLYNOMIAL,approxargs);
740 }
741 else{
742 L->funcs[kk] =
743 generic_function_daxpby(1.0/val,A->funcs[kk],
744 0.0, NULL);
745 }
746 for (ii = 0; ii < A->n; ii++){
747
748 u[ii*A->n+kk] =
749 generic_function_1d_eval(A->funcs[ii], amloc);
750 temp = generic_function_daxpby(1.0, A->funcs[ii],
751 -u[ii*A->n+kk],
752 L->funcs[kk]);
753 generic_function_free(A->funcs[ii]);
754 A->funcs[ii] = generic_function_daxpby(1.0,
755 temp,
756 0.0, NULL);
757 generic_function_free(temp); temp = NULL;
758 }
759 }
760
761 // check if matrix is full rank
762 for (kk = 0; kk < A->n; kk++){
763 if (fabs(u[kk*A->n + kk]) < ZEROTHRESH){
764 info --;
765 }
766 }
767
768 return info;
769 }
770
771 /*********************************************************//**
772 Perform a greedy maximum volume procedure to find the
773 maximum volume submatrix of quasimatrix
774
775 \param[in] A - quasimatrix
776 \param[in,out] Asinv - submatrix inv
777 \param[in,out] p - pivots
778 \param[in] approxargs - approximation arguments for each column
779 \param[in] optargs - optimization arguments
780
781
782 \return info
783
784 \note
785 info =
786 - 0 converges
787 - < 0 no invertible submatrix
788 - >0 rank may be too high
789 naive implementation without rank 1 updates
790 *************************************************************/
quasimatrix_maxvol1d(struct Quasimatrix * A,double * Asinv,double * p,void * approxargs,void * optargs)791 int quasimatrix_maxvol1d(struct Quasimatrix * A,
792 double * Asinv, double * p,
793 void * approxargs, void * optargs)
794 {
795 int info = 0;
796 double delta = 0.01;
797 size_t r = A->n;
798
799 struct Quasimatrix * L = quasimatrix_alloc(r);
800 double * U = calloc_double(r * r);
801
802 double *eye = calloc_double(r * r);
803 size_t ii;
804 for (ii = 0; ii < r; ii++){
805 eye[ii*r + ii] = 1.0;
806 }
807 struct Quasimatrix * Acopy = qmm(A,eye,r);
808
809 info = quasimatrix_lu1d(Acopy,L,U,p,approxargs,optargs);
810 //printf("pivot immediate \n");
811 //dprint(A->n, p);
812
813 if (info != 0){
814 printf("Couldn't find an invertible submatrix for maxvol %d\n",info);
815 //printf("Couldn't Error from quasimatrix_lu1d \n");
816 quasimatrix_free(L);
817 quasimatrix_free(Acopy);
818 free(U);
819 free(eye);
820 return info;
821 }
822
823 size_t jj;
824 for (ii = 0; ii < r; ii++){
825 for (jj = 0; jj < r; jj++){
826 Asinv[jj * r + ii] =
827 generic_function_1d_eval(A->funcs[jj],p[ii]);
828 }
829 }
830
831 int * ipiv2 = calloc(r, sizeof(int));
832 size_t lwork = r*r;
833 double * work = calloc(lwork, sizeof(double));
834 int info2;
835
836 dgetrf_((int*)&r,(int*)&r, Asinv, (int*)&r, ipiv2, &info2);
837 dgetri_((int*)&r, Asinv, (int*)&r, ipiv2, work, (int*)&lwork, &info2); //invert
838
839 struct Quasimatrix * B = qmm(A,Asinv,r);
840 size_t maxcol;
841 double maxloc, maxval;
842 maxcol = quasimatrix_absmax(B,&maxloc,&maxval,NULL);
843
844 while (maxval > (1.0 + delta)){
845 //printf("maxval = %3.4f\n", maxval);
846 p[maxcol] = maxloc;
847 for (ii = 0; ii < r; ii++){
848 for (jj = 0; jj < r; jj++){
849 Asinv[jj * r + ii] =
850 generic_function_1d_eval(A->funcs[jj],p[ii]);
851 }
852 }
853
854 dgetrf_((int*)&r,(int*)&r, Asinv, (int*)&r, ipiv2, &info2);
855 //invert
856 dgetri_((int*)&r, Asinv, (int*)&r, ipiv2, work, (int*)&lwork, &info2);
857 quasimatrix_free(B);
858 B = qmm(A,Asinv,r);
859 maxcol = quasimatrix_absmax(B,&maxloc,&maxval,NULL);
860 }
861 //printf("maxval = %3.4f\n", maxval);
862
863 free(work);
864 free(ipiv2);
865 quasimatrix_free(B);
866 quasimatrix_free(L);
867 quasimatrix_free(Acopy);
868 free(U);
869 free(eye);
870 return info;
871 }
872
873 /*********************************************************//**
874 Compute rank of a quasimatrix
875
876 \param[in] A - quasimatrix
877 \param[in] opts - options for QR decomposition
878
879 \return rank
880 *************************************************************/
quasimatrix_rank(const struct Quasimatrix * A,void * opts)881 size_t quasimatrix_rank(const struct Quasimatrix * A, void * opts)
882 {
883 size_t rank = A->n;
884 size_t ncols = A->n;
885 /* enum poly_type ptype = LEGENDRE; */
886 // generate two quasimatrices needed for householder
887 //
888 /* double lb = generic_function_get_lower_bound(A->funcs[0]); */
889 /* double ub = generic_function_get_upper_bound(A->funcs[0]); */
890
891 struct Quasimatrix * Q = quasimatrix_orth1d(ncols,POLYNOMIAL, opts);
892
893 struct Quasimatrix * V = quasimatrix_alloc(ncols);
894 double * R = calloc_double(rank * rank);
895
896 double * eye = calloc_double(rank * rank);
897 size_t ii;
898 for (ii = 0; ii < rank; ii++){
899 eye[ii * rank + ii] = 1.0;
900 }
901 struct Quasimatrix * qm = quasimatrix_copy(A);
902 int out = 0;
903 out = quasimatrix_householder(qm,Q,V,R);
904
905 assert(out == 0);
906 /* dprint2d_col(qm->n,qm->n,R); */
907 for (ii = 0; ii < qm->n; ii++){
908 if (fabs(R[ii * qm->n + ii]) < 10.0*ZEROTHRESH){
909 rank = rank - 1;
910 }
911 }
912
913 quasimatrix_free(Q);
914 quasimatrix_free(V);
915 quasimatrix_free(qm);
916 free(eye);
917 free(R);
918 return rank;
919 }
920
921 /*********************************************************//**
922 Compute norm of a quasimatrix
923
924 \param[in] A - quasimatrix
925
926 \return mag - norm of the quasimatrix
927 *************************************************************/
quasimatrix_norm(const struct Quasimatrix * A)928 double quasimatrix_norm(const struct Quasimatrix * A)
929 {
930 double mag = sqrt(quasimatrix_inner(A,A));
931 return mag;
932 }
933
934 //////////////////////////////////////////////
935 // Local functions
936 /* static void quasimatrix_flip_sign(struct Quasimatrix * x) */
937 /* { */
938 /* size_t ii; */
939 /* for (ii = 0; ii < x->n; ii++){ */
940 /* generic_function_flip_sign(x->funcs[ii]); */
941 /* } */
942 /* } */
943
quasimatrix_print(const struct Quasimatrix * qm,FILE * fp,size_t prec,void * args)944 void quasimatrix_print(const struct Quasimatrix * qm,FILE *fp,
945 size_t prec, void * args)
946 {
947 (void)(fp);
948 printf("Quasimatrix consists of %zu columns\n",qm->n);
949 printf("=========================================\n");
950 size_t ii;
951 for (ii = 0; ii < qm->n; ii++){
952 print_generic_function(qm->funcs[ii],prec,args, fp);
953 printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
954 }
955 }
956