Main MRPT website > C++ reference for MRPT 1.5.3
cs.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | http://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2017, Individual contributors, see AUTHORS file |
6  | See: http://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See details in http://www.mrpt.org/License |
8  +---------------------------------------------------------------------------+ */
9 #ifndef _CS_H
10 #define _CS_H
11 #include <stdlib.h>
12 #include <limits.h>
13 #include <math.h>
14 #include <stdio.h>
15 #ifdef MATLAB_MEX_FILE
16 #include "mex.h"
17 #endif
18 #define CS_VER 2 /* CSparse Version */
19 #define CS_SUBVER 2
20 #define CS_SUBSUB 4
21 #define CS_DATE "Nov 30, 2009" /* CSparse release date */
22 #define CS_COPYRIGHT "Copyright (c) Timothy A. Davis, 2006-2009"
23 
24 /* --- primary CSparse routines and data structures ------------------------- */
25 typedef struct cs_sparse /* matrix in compressed-column or triplet form */
26 {
27  int nzmax ; /* maximum number of entries */
28  int m ; /* number of rows */
29  int n ; /* number of columns */
30  int *p ; /* column pointers (size n+1) or col indices (size nzmax) */
31  int *i ; /* row indices, size nzmax */
32  double *x ; /* numerical values, size nzmax */
33  int nz ; /* # of entries in triplet matrix, -1 for compressed-col */
34 } cs ;
35 
36 cs *cs_add (const cs *A, const cs *B, double alpha, double beta) ;
37 int cs_cholsol (int order, const cs *A, double *b) ;
38 cs *cs_compress (const cs *T) ;
39 int cs_dupl (cs *A) ;
40 int cs_entry (cs *T, int i, int j, double x) ;
41 int cs_gaxpy (const cs *A, const double *x, double *y) ;
42 cs *cs_load (FILE *f) ;
43 int cs_lusol (int order, const cs *A, double *b, double tol) ;
44 cs *cs_multiply (const cs *A, const cs *B) ;
45 double cs_norm (const cs *A) ;
46 int cs_print (const cs *A, int brief) ;
47 int cs_qrsol (int order, const cs *A, double *b) ;
48 cs *cs_transpose (const cs *A, int values) ;
49 /* utilities */
50 void *cs_calloc (int n, size_t size) ;
51 void *cs_free (void *p) ;
52 void *cs_realloc (void *p, int n, size_t size, int *ok) ;
53 cs *cs_spalloc (int m, int n, int nzmax, int values, int triplet) ;
54 cs *cs_spfree (cs *A) ;
55 int cs_sprealloc (cs *A, int nzmax) ;
56 void *cs_malloc (int n, size_t size) ;
57 
58 /* --- secondary CSparse routines and data structures ----------------------- */
59 typedef struct cs_symbolic /* symbolic Cholesky, LU, or QR analysis */
60 {
61  int *pinv ; /* inverse row perm. for QR, fill red. perm for Chol */
62  int *q ; /* fill-reducing column permutation for LU and QR */
63  int *parent ; /* elimination tree for Cholesky and QR */
64  int *cp ; /* column pointers for Cholesky, row counts for QR */
65  int *leftmost ; /* leftmost[i] = min(find(A(i,:))), for QR */
66  int m2 ; /* # of rows for QR, after adding fictitious rows */
67  double lnz ; /* # entries in L for LU or Cholesky; in V for QR */
68  double unz ; /* # entries in U for LU; in R for QR */
69 } css ;
70 
71 typedef struct cs_numeric /* numeric Cholesky, LU, or QR factorization */
72 {
73  cs *L ; /* L for LU and Cholesky, V for QR */
74  cs *U ; /* U for LU, R for QR, not used for Cholesky */
75  int *pinv ; /* partial pivoting for LU */
76  double *B ; /* beta [0..n-1] for QR */
77 } csn ;
78 
79 typedef struct cs_dmperm_results /* cs_dmperm or cs_scc output */
80 {
81  int *p ; /* size m, row permutation */
82  int *q ; /* size n, column permutation */
83  int *r ; /* size nb+1, block k is rows r[k] to r[k+1]-1 in A(p,q) */
84  int *s ; /* size nb+1, block k is cols s[k] to s[k+1]-1 in A(p,q) */
85  int nb ; /* # of blocks in fine dmperm decomposition */
86  int rr [5] ; /* coarse row decomposition */
87  int cc [5] ; /* coarse column decomposition */
88 } csd ;
89 
90 int *cs_amd (int order, const cs *A) ;
91 csn *cs_chol (const cs *A, const css *S) ;
92 csd *cs_dmperm (const cs *A, int seed) ;
93 int cs_droptol (cs *A, double tol) ;
94 int cs_dropzeros (cs *A) ;
95 int cs_happly (const cs *V, int i, double beta, double *x) ;
96 int cs_ipvec (const int *p, const double *b, double *x, int n) ;
97 int cs_lsolve (const cs *L, double *x) ;
98 int cs_ltsolve (const cs *L, double *x) ;
99 csn *cs_lu (const cs *A, const css *S, double tol) ;
100 cs *cs_permute (const cs *A, const int *pinv, const int *q, int values) ;
101 int *cs_pinv (const int *p, int n) ;
102 int cs_pvec (const int *p, const double *b, double *x, int n) ;
103 csn *cs_qr (const cs *A, const css *S) ;
104 css *cs_schol (int order, const cs *A) ;
105 css *cs_sqr (int order, const cs *A, int qr) ;
106 cs *cs_symperm (const cs *A, const int *pinv, int values) ;
107 int cs_updown (cs *L, int sigma, const cs *C, const int *parent) ;
108 int cs_usolve (const cs *U, double *x) ;
109 int cs_utsolve (const cs *U, double *x) ;
110 /* utilities */
111 css *cs_sfree (css *S) ;
112 csn *cs_nfree (csn *N) ;
113 csd *cs_dfree (csd *D) ;
114 
115 /* --- tertiary CSparse routines -------------------------------------------- */
116 int *cs_counts (const cs *A, const int *parent, const int *post, int ata) ;
117 double cs_cumsum (int *p, int *c, int n) ;
118 int cs_dfs (int j, cs *G, int top, int *xi, int *pstack, const int *pinv) ;
119 int cs_ereach (const cs *A, int k, const int *parent, int *s, int *w) ;
120 int *cs_etree (const cs *A, int ata) ;
121 int cs_fkeep (cs *A, int (*fkeep) (int, int, double, void *), void *other) ;
122 double cs_house (double *x, double *beta, int n) ;
123 int cs_leaf (int i, int j, const int *first, int *maxfirst, int *prevleaf,
124  int *ancestor, int *jleaf) ;
125 int *cs_maxtrans (const cs *A, int seed) ;
126 int *cs_post (const int *parent, int n) ;
127 int *cs_randperm (int n, int seed) ;
128 int cs_reach (cs *G, const cs *B, int k, int *xi, const int *pinv) ;
129 int cs_scatter (const cs *A, int j, double beta, int *w, double *x, int mark,
130  cs *C, int nz) ;
131 csd *cs_scc (cs *A) ;
132 int cs_spsolve (cs *G, const cs *B, int k, int *xi, double *x,
133  const int *pinv, int lo) ;
134 int cs_tdfs (int j, int k, int *head, const int *next, int *post,
135  int *stack) ;
136 /* utilities */
137 csd *cs_dalloc (int m, int n) ;
138 csd *cs_ddone (csd *D, cs *C, void *w, int ok) ;
139 cs *cs_done (cs *C, void *w, void *x, int ok) ;
140 int *cs_idone (int *p, cs *C, void *w, int ok) ;
141 csn *cs_ndone (csn *N, cs *C, void *w, void *x, int ok) ;
142 
143 #define CS_MAX(a,b) (((a) > (b)) ? (a) : (b))
144 #define CS_MIN(a,b) (((a) < (b)) ? (a) : (b))
145 #define CS_FLIP(i) (-(i)-2)
146 #define CS_UNFLIP(i) (((i) < 0) ? CS_FLIP(i) : (i))
147 #define CS_MARKED(w,j) (w [j] < 0)
148 #define CS_MARK(w,j) { w [j] = CS_FLIP (w [j]) ; }
149 #define CS_CSC(A) (A && (A->nz == -1))
150 #define CS_TRIPLET(A) (A && (A->nz >= 0))
151 #endif
css * cs_sqr(int order, const cs *A, int qr)
int cs_lusol(int order, const cs *A, double *b, double tol)
int cs_reach(cs *G, const cs *B, int k, int *xi, const int *pinv)
int cs_dupl(cs *A)
cs * cs_load(FILE *f)
csn * cs_chol(const cs *A, const css *S)
int * pinv
Definition: cs.h:75
int cs_lsolve(const cs *L, double *x)
size_t size(const MATRIXLIKE &m, const int dim)
Definition: bits.h:43
struct cs_dmperm_results csd
double * B
Definition: cs.h:76
csn * cs_nfree(csn *N)
cs * cs_spfree(cs *A)
cs * cs_spalloc(int m, int n, int nzmax, int values, int triplet)
int cs_ltsolve(const cs *L, double *x)
csn * cs_qr(const cs *A, const css *S)
int * s
Definition: cs.h:84
cs * cs_done(cs *C, void *w, void *x, int ok)
cs * cs_symperm(const cs *A, const int *pinv, int values)
cs * cs_permute(const cs *A, const int *pinv, const int *q, int values)
int cs_droptol(cs *A, double tol)
int n
Definition: cs.h:29
cs * U
Definition: cs.h:74
csd * cs_dalloc(int m, int n)
csd * cs_dmperm(const cs *A, int seed)
void * cs_free(void *p)
int * cs_post(const int *parent, int n)
int cs_fkeep(cs *A, int(*fkeep)(int, int, double, void *), void *other)
struct cs_numeric csn
double cs_house(double *x, double *beta, int n)
double lnz
Definition: cs.h:67
int cs_qrsol(int order, const cs *A, double *b)
Definition: cs.h:71
int cs_ipvec(const int *p, const double *b, double *x, int n)
cs * cs_transpose(const cs *A, int values)
int nzmax
Definition: cs.h:27
int cs_usolve(const cs *U, double *x)
int cs_dfs(int j, cs *G, int top, int *xi, int *pstack, const int *pinv)
int cs_print(const cs *A, int brief)
int cs_happly(const cs *V, int i, double beta, double *x)
int cs_sprealloc(cs *A, int nzmax)
int cs_ereach(const cs *A, int k, const int *parent, int *s, int *w)
double unz
Definition: cs.h:68
csd * cs_dfree(csd *D)
int * cs_etree(const cs *A, int ata)
struct cs_sparse cs
int nz
Definition: cs.h:33
int cs_utsolve(const cs *U, double *x)
int cs_leaf(int i, int j, const int *first, int *maxfirst, int *prevleaf, int *ancestor, int *jleaf)
struct cs_symbolic css
int * cs_maxtrans(const cs *A, int seed)
int * leftmost
Definition: cs.h:65
int * cs_idone(int *p, cs *C, void *w, int ok)
int cs_entry(cs *T, int i, int j, double x)
cs * cs_add(const cs *A, const cs *B, double alpha, double beta)
int * p
Definition: cs.h:30
double cs_norm(const cs *A)
int cs_scatter(const cs *A, int j, double beta, int *w, double *x, int mark, cs *C, int nz)
Definition: cs.h:25
int * i
Definition: cs.h:31
int * cp
Definition: cs.h:64
void * cs_calloc(int n, size_t size)
int cs_pvec(const int *p, const double *b, double *x, int n)
int * pinv
Definition: cs.h:61
double cs_cumsum(int *p, int *c, int n)
cs * cs_multiply(const cs *A, const cs *B)
int * q
Definition: cs.h:62
int cs_tdfs(int j, int k, int *head, const int *next, int *post, int *stack)
cs * cs_compress(const cs *T)
csd * cs_ddone(csd *D, cs *C, void *w, int ok)
void * cs_malloc(int n, size_t size)
csd * cs_scc(cs *A)
int cs_cholsol(int order, const cs *A, double *b)
void * cs_realloc(void *p, int n, size_t size, int *ok)
int * cs_amd(int order, const cs *A)
int * p
Definition: cs.h:81
int * r
Definition: cs.h:83
int cs_dropzeros(cs *A)
int m2
Definition: cs.h:66
int * cs_pinv(const int *p, int n)
double * x
Definition: cs.h:32
css * cs_sfree(css *S)
int * parent
Definition: cs.h:63
csn * cs_ndone(csn *N, cs *C, void *w, void *x, int ok)
int cs_gaxpy(const cs *A, const double *x, double *y)
csn * cs_lu(const cs *A, const css *S, double tol)
css * cs_schol(int order, const cs *A)
int cs_spsolve(cs *G, const cs *B, int k, int *xi, double *x, const int *pinv, int lo)
int * cs_randperm(int n, int seed)
int cs_updown(cs *L, int sigma, const cs *C, const int *parent)
int * q
Definition: cs.h:82
int m
Definition: cs.h:28
int * cs_counts(const cs *A, const int *parent, const int *post, int ata)
cs * L
Definition: cs.h:73
Definition: cs.h:59



Page generated by Doxygen 1.8.13 for MRPT 1.5.3 at Mon Oct 30 10:27:08 UTC 2017