/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <cs/cs.h> #include <igraph.h> #include <igraph_sparsemat.h> igraph_bool_t check_solution(const igraph_sparsemat_t *A, const igraph_vector_t *x, const igraph_vector_t *b) { long int dim=igraph_vector_size(x); igraph_vector_t res; int j, p; igraph_real_t min, max; igraph_vector_copy(&res, b); for (j=0; j<dim; j++) { for (p=A->cs->p[j]; p < A->cs->p[j+1]; p++) { long int from=A->cs->i[p]; igraph_real_t value=A->cs->x[p]; VECTOR(res)[from] -= VECTOR(*x)[j] * value; } } igraph_vector_minmax(&res, &min, &max); igraph_vector_destroy(&res); return abs(min) < 1e-15 && abs(max) < 1e-15; } int main() { igraph_sparsemat_t A, B, C; igraph_vector_t b, x; long int i; /* lsolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES+DIM); for (i=0; i<DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1,3)); } for (i=0; i<EDGES; i++) { long int r=RNG_INTEGER(0, DIM-1); long int c=RNG_INTEGER(0, r); igraph_real_t value=RNG_INTEGER(1,5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_vector_init(&b, DIM); for (i=0; i<DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1,10); } igraph_vector_init(&x, DIM); igraph_sparsemat_lsolve(&B, &b, &x); if (! check_solution(&B, &x, &b)) { return 1; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); #undef DIM #undef EDGES /* ltsolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES+DIM); for (i=0; i<DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1,3)); } for (i=0; i<EDGES; i++) { long int r=RNG_INTEGER(0, DIM-1); long int c=RNG_INTEGER(0, r); igraph_real_t value=RNG_INTEGER(1,5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_vector_init(&b, DIM); for (i=0; i<DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1,10); } igraph_vector_init(&x, DIM); igraph_sparsemat_ltsolve(&B, &b, &x); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); if (! check_solution(&A, &x, &b)) { return 2; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); #undef DIM #undef EDGES /* usolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES+DIM); for (i=0; i<DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1,3)); } for (i=0; i<EDGES; i++) { long int r=RNG_INTEGER(0, DIM-1); long int c=RNG_INTEGER(0, r); igraph_real_t value=RNG_INTEGER(1,5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); igraph_vector_init(&b, DIM); for (i=0; i<DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1,10); } igraph_vector_init(&x, DIM); igraph_sparsemat_usolve(&A, &b, &x); if (! check_solution(&A, &x, &b)) { return 3; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); #undef DIM #undef EDGES /* utsolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES+DIM); for (i=0; i<DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1,3)); } for (i=0; i<EDGES; i++) { long int r=RNG_INTEGER(0, DIM-1); long int c=RNG_INTEGER(0, r); igraph_real_t value=RNG_INTEGER(1,5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); igraph_sparsemat_destroy(&B); igraph_vector_init(&b, DIM); for (i=0; i<DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1,10); } igraph_vector_init(&x, DIM); igraph_sparsemat_utsolve(&A, &b, &x); igraph_sparsemat_transpose(&A, &B, /*values=*/ 1); if (! check_solution(&B, &x, &b)) { return 4; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); #undef DIM #undef EDGES /* cholsol */ /* We need a positive definite matrix, so we create a full-rank matrix first and then calculate A'A, which will be positive definite. */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES+DIM); for (i=0; i<DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1,3)); } for (i=0; i<EDGES; i++) { long int from=RNG_INTEGER(0, DIM-1); long int to=RNG_INTEGER(0, DIM-1); igraph_real_t value=RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, from, to, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); igraph_sparsemat_multiply(&A, &B, &C); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); igraph_vector_init(&b, DIM); for (i=0; i<DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1,10); } igraph_vector_init(&x, DIM); igraph_sparsemat_cholsol(&C, &b, &x, /*order=*/ 0); if (! check_solution(&C, &x, &b)) { return 5; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&C); #undef DIM #undef EDGES /* lusol */ #define DIM 10 #define EDGES (DIM*DIM/4) igraph_sparsemat_init(&A, DIM, DIM, EDGES+DIM); for (i=0; i<DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1,3)); } for (i=0; i<EDGES; i++) { long int from=RNG_INTEGER(0, DIM-1); long int to=RNG_INTEGER(0, DIM-1); igraph_real_t value=RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, from, to, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_vector_init(&b, DIM); for (i=0; i<DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1,10); } igraph_vector_init(&x, DIM); igraph_sparsemat_lusol(&B, &b, &x, /*order=*/ 0, /*tol=*/ 1e-10); if (! check_solution(&B, &x, &b)) { return 6; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); #undef DIM #undef EDGES return 0; }