1 /* 2 * This file is part of CasADi. 3 * 4 * CasADi -- A symbolic framework for dynamic optimization. 5 * Copyright (C) 2010-2014 Joel Andersson, Joris Gillis, Moritz Diehl, 6 * K.U. Leuven. All rights reserved. 7 * Copyright (C) 2011-2014 Greg Horn 8 * Copyright (C) 2005-2013 Timothy A. Davis 9 * 10 * CasADi is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU Lesser General Public 12 * License as published by the Free Software Foundation; either 13 * version 3 of the License, or (at your option) any later version. 14 * 15 * CasADi is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * Lesser General Public License for more details. 19 * 20 * You should have received a copy of the GNU Lesser General Public 21 * License along with CasADi; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 23 * 24 */ 25 26 27 #include "sparsity_internal.hpp" 28 #include "casadi_misc.hpp" 29 #include "global_options.hpp" 30 #include <climits> 31 #include <cstdlib> 32 #include <cmath> 33 34 using namespace std; 35 36 namespace casadi { etree(const casadi_int * sp,casadi_int * parent,casadi_int * w,casadi_int ata)37 void SparsityInternal::etree(const casadi_int* sp, casadi_int* parent, 38 casadi_int *w, casadi_int ata) { 39 /* 40 Modified version of cs_etree in CSparse 41 Copyright(c) Timothy A. Davis, 2006-2009 42 Licensed as a derivative work under the GNU LGPL 43 */ 44 casadi_int r, c, k, rnext; 45 // Extract sparsity 46 casadi_int nrow = *sp++, ncol = *sp++; 47 const casadi_int *colind = sp, *row = sp+ncol+1; 48 // Highest known ascestor of a node 49 casadi_int *ancestor=w; 50 // Path for A'A 51 casadi_int *prev; 52 if (ata) { 53 prev=w+ncol; 54 for (r=0; r<nrow; ++r) prev[r] = -1; 55 } 56 // Loop over columns 57 for (c=0; c<ncol; ++c) { 58 parent[c] = -1; // No parent yet 59 ancestor[c] = -1; // No ancestor 60 // Loop over nonzeros 61 for (k=colind[c]; k<colind[c+1]; ++k) { 62 r = row[k]; 63 if (ata) r = prev[r]; 64 // Traverse from r to c 65 while (r!=-1 && r<c) { 66 rnext = ancestor[r]; 67 ancestor[r] = c; 68 if (rnext==-1) parent[r] = c; 69 r = rnext; 70 } 71 if (ata) prev[row[k]] = c; 72 } 73 } 74 } 75 postorder_dfs(casadi_int j,casadi_int k,casadi_int * head,const casadi_int * next,casadi_int * post,casadi_int * stack)76 casadi_int SparsityInternal::postorder_dfs(casadi_int j, casadi_int k, 77 casadi_int* head, const casadi_int* next, 78 casadi_int* post, casadi_int* stack) { 79 /* Modified version of cs_tdfs in CSparse 80 Copyright(c) Timothy A. Davis, 2006-2009 81 Licensed as a derivative work under the GNU LGPL 82 */ 83 casadi_int i, p, top=0; 84 stack[0] = j; 85 while (top>=0) { 86 p = stack[top]; 87 i = head[p]; 88 if (i==-1) { 89 // No children 90 top--; 91 post[k++] = p; 92 } else { 93 // Add to stack 94 head[p] = next[i]; 95 stack[++top] = i; 96 } 97 } 98 return k; 99 } 100 postorder(const casadi_int * parent,casadi_int n,casadi_int * post,casadi_int * w)101 void SparsityInternal::postorder(const casadi_int* parent, casadi_int n, 102 casadi_int* post, casadi_int* w) { 103 /* Modified version of cs_post in CSparse 104 Copyright(c) Timothy A. Davis, 2006-2009 105 Licensed as a derivative work under the GNU LGPL 106 */ 107 casadi_int j, k=0; 108 // Work vectors 109 casadi_int *head, *next, *stack; 110 head=w; w+=n; 111 next=w; w+=n; 112 stack=w; w+=n; 113 // Empty linked lists 114 for (j=0; j<n; ++j) head[j] = -1; 115 // Traverse nodes in reverse order 116 for (j=n-1; j>=0; --j) { 117 if (parent[j]!=-1) { 118 next[j] = head[parent[j]]; 119 head[parent[j]] = j; 120 } 121 } 122 for (j=0; j<n; j++) { 123 if (parent[j]==-1) { 124 k = postorder_dfs(j, k, head, next, post, stack); 125 } 126 } 127 } 128 129 casadi_int SparsityInternal:: leaf(casadi_int i,casadi_int j,const casadi_int * first,casadi_int * maxfirst,casadi_int * prevleaf,casadi_int * ancestor,casadi_int * jleaf)130 leaf(casadi_int i, casadi_int j, const casadi_int* first, casadi_int* maxfirst, 131 casadi_int* prevleaf, casadi_int* ancestor, casadi_int* jleaf) { 132 /* Modified version of cs_leaf in CSparse 133 Copyright(c) Timothy A. Davis, 2006-2009 134 Licensed as a derivative work under the GNU LGPL 135 */ 136 casadi_int q, s, sparent, jprev; 137 *jleaf = 0; 138 // Quick return if j is not a leaf 139 if (i<=j || first[j]<=maxfirst[i]) return -1; 140 // Update max first[j] seen so far 141 maxfirst[i] = first[j]; 142 // Previous leaf of ith subtree 143 jprev = prevleaf[i]; 144 prevleaf[i] = j; 145 // j is first or subsequent leaf 146 *jleaf = (jprev == -1) ? 1 : 2; 147 // if first leaf, q is root of ith subtree 148 if (*jleaf==1) return i; 149 // Path compression 150 for (q=jprev; q!=ancestor[q]; q=ancestor[q]) {} 151 for (s=jprev; s!=q; s=sparent) { 152 sparent = ancestor[s]; 153 ancestor[s] = q; 154 } 155 // Return least common ancestor 156 return q; 157 } 158 159 casadi_int SparsityInternal:: qr_counts(const casadi_int * tr_sp,const casadi_int * parent,const casadi_int * post,casadi_int * counts,casadi_int * w)160 qr_counts(const casadi_int* tr_sp, const casadi_int* parent, 161 const casadi_int* post, casadi_int* counts, casadi_int* w) { 162 /* Modified version of cs_counts in CSparse 163 Copyright(c) Timothy A. Davis, 2006-2009 164 Licensed as a derivative work under the GNU LGPL 165 */ 166 casadi_int ncol = *tr_sp++, nrow = *tr_sp++; 167 const casadi_int *rowind=tr_sp, *col=tr_sp+nrow+1; 168 casadi_int i, j, k, J, p, q, jleaf, *maxfirst, *prevleaf, 169 *ancestor, *head=nullptr, *next=nullptr, *first; 170 // Work vectors 171 ancestor=w; w+=ncol; 172 maxfirst=w; w+=ncol; 173 prevleaf=w; w+=ncol; 174 first=w; w+=ncol; 175 head=w; w+=ncol+1; 176 next=w; w+=nrow; 177 // Find first [j] 178 for (k=0; k<ncol; ++k) first[k]=-1; 179 for (k=0; k<ncol; ++k) { 180 j=post[k]; 181 // counts[j]=1 if j is a leaf 182 counts[j] = (first[j]==-1) ? 1 : 0; 183 for (; j!=-1 && first[j]==-1; j=parent[j]) first[j]=k; 184 } 185 // Invert post (use ancestor as work vector) 186 for (k=0; k<ncol; ++k) ancestor[post[k]] = k; 187 for (k=0; k<ncol+1; ++k) head[k]=-1; 188 for (i=0; i<nrow; ++i) { 189 for (k=ncol, p=rowind[i]; p<rowind[i+1]; ++p) { 190 k = std::min(k, ancestor[col[p]]); 191 } 192 // Place row i in linked list k 193 next[i] = head[k]; 194 head[k] = i; 195 } 196 197 // Clear workspace 198 for (k=0; k<ncol; ++k) maxfirst[k]=-1; 199 for (k=0; k<ncol; ++k) prevleaf[k]=-1; 200 // Each node in its own set 201 for (i=0; i<ncol; ++i) ancestor[i]=i; 202 for (k=0; k<ncol; ++k) { 203 // j is the kth node in the postordered etree 204 j=post[k]; 205 if (parent[j]!=-1) counts[parent[j]]--; // j is not a root 206 J=head[k]; 207 while (J!=-1) { // J=j for LL' = A case 208 for (p=rowind[J]; p<rowind[J+1]; ++p) { 209 i=col[p]; 210 q = leaf(i, j, first, maxfirst, prevleaf, ancestor, &jleaf); 211 if (jleaf>=1) counts[j]++; // A(i,j) is in skeleton 212 if (jleaf==2) counts[q]--; // account for overlap in q 213 } 214 J = next[J]; 215 } 216 if (parent[j]!=-1) ancestor[j]=parent[j]; 217 } 218 // Sum up counts of each child 219 for (j=0; j<ncol; ++j) { 220 if (parent[j]!=-1) counts[parent[j]] += counts[j]; 221 } 222 223 // Sum of counts 224 casadi_int sum_counts = 0; 225 for (j=0; j<ncol; ++j) sum_counts += counts[j]; 226 return sum_counts; 227 } 228 229 casadi_int SparsityInternal:: qr_nnz(const casadi_int * sp,casadi_int * pinv,casadi_int * leftmost,const casadi_int * parent,casadi_int * nrow_ext,casadi_int * w)230 qr_nnz(const casadi_int* sp, casadi_int* pinv, casadi_int* leftmost, 231 const casadi_int* parent, casadi_int* nrow_ext, casadi_int* w) { 232 /* Modified version of cs_sqr in CSparse 233 Copyright(c) Timothy A. Davis, 2006-2009 234 Licensed as a derivative work under the GNU LGPL 235 */ 236 // Extract sparsity 237 casadi_int nrow = sp[0], ncol = sp[1]; 238 const casadi_int *colind=sp+2, *row=sp+2+ncol+1; 239 // Work vectors 240 casadi_int *next=w; w+=nrow; 241 casadi_int *head=w; w+=ncol; 242 casadi_int *tail=w; w+=ncol; 243 casadi_int *nque=w; w+=ncol; 244 // Local variables 245 casadi_int r, c, k, pa; 246 // Clear queue 247 for (c=0; c<ncol; ++c) head[c] = -1; 248 for (c=0; c<ncol; ++c) tail[c] = -1; 249 for (c=0; c<ncol; ++c) nque[c] = 0; 250 for (r=0; r<nrow; ++r) leftmost[r] = -1; 251 // leftmost[r] = min(find(A(r,:))) 252 for (c=ncol-1; c>=0; --c) { 253 for (k=colind[c]; k<colind[c+1]; ++k) { 254 leftmost[row[k]] = c; 255 } 256 } 257 // Scan rows in reverse order 258 for (r=nrow-1; r>=0; --r) { 259 pinv[r] = -1; // row r not yet ordered 260 c=leftmost[r]; 261 262 if (c==-1) continue; // row r is empty 263 if (nque[c]++ == 0) tail[c]=r; // first row in queue c 264 next[r] = head[c]; // put r at head of queue c 265 head[c] = r; 266 } 267 // Find row permutation and nnz(V) 268 casadi_int v_nnz = 0; 269 casadi_int nrow_new = nrow; 270 for (c=0; c<ncol; ++c) { 271 r = head[c]; // remove r from queue c 272 v_nnz++; // count V(c,c) as nonzero 273 if (r<0) r=nrow_new++; // add a fictitious row 274 pinv[r] = c; // associate row r with V(:,c) 275 if (--nque[c]<=0) continue; // skip if V(c+1,nrow,c) is empty 276 v_nnz += nque[c]; // nque[c] is nnz(V(c+1:nrow, c)) 277 if ((pa=parent[c]) != -1) { 278 // Move all rows to parent of c 279 if (nque[pa]==0) tail[pa] = tail[c]; 280 next[tail[c]] = head[pa]; 281 head[pa] = next[r]; 282 nque[pa] += nque[c]; 283 } 284 } 285 for (r=0; r<nrow; ++r) if (pinv[r]<0) pinv[r] = c++; 286 if (nrow_ext) *nrow_ext = nrow_new; 287 return v_nnz; 288 } 289 290 void SparsityInternal:: qr_init(const casadi_int * sp,const casadi_int * sp_tr,casadi_int * leftmost,casadi_int * parent,casadi_int * pinv,casadi_int * nrow_ext,casadi_int * v_nnz,casadi_int * r_nnz,casadi_int * w)291 qr_init(const casadi_int* sp, const casadi_int* sp_tr, 292 casadi_int* leftmost, casadi_int* parent, casadi_int* pinv, 293 casadi_int* nrow_ext, casadi_int* v_nnz, casadi_int* r_nnz, casadi_int* w) { 294 // Extract sparsity 295 casadi_int ncol = sp[1]; 296 // Calculate elimination tree for A'A 297 etree(sp, parent, w, 1); // len[w] >= nrow+ncol 298 // Calculate postorder 299 casadi_int* post = w; w += ncol; 300 postorder(parent, ncol, post, w); // len[w] >= 3*ncol 301 // Calculate nnz in R 302 *r_nnz = qr_counts(sp_tr, parent, post, w, w+ncol); 303 // Calculate nnz in V 304 *v_nnz = qr_nnz(sp, pinv, leftmost, parent, nrow_ext, w); 305 } 306 307 void SparsityInternal:: qr_sparsities(const casadi_int * sp_a,casadi_int nrow_ext,casadi_int * sp_v,casadi_int * sp_r,const casadi_int * leftmost,const casadi_int * parent,const casadi_int * pinv,casadi_int * iw)308 qr_sparsities(const casadi_int* sp_a, casadi_int nrow_ext, casadi_int* sp_v, casadi_int* sp_r, 309 const casadi_int* leftmost, const casadi_int* parent, const casadi_int* pinv, 310 casadi_int* iw) { 311 /* Modified version of cs_qr in CSparse 312 Copyright(c) Timothy A. Davis, 2006-2009 313 Licensed as a derivative work under the GNU LGPL 314 */ 315 // Extract sparsities 316 casadi_int ncol = sp_a[1]; 317 const casadi_int *colind=sp_a+2, *row=sp_a+2+ncol+1; 318 casadi_int *v_colind=sp_v+2, *v_row=sp_v+2+ncol+1; 319 casadi_int *r_colind=sp_r+2, *r_row=sp_r+2+ncol+1; 320 // Specify dimensions of V and R 321 sp_v[0] = sp_r[0] = nrow_ext; 322 sp_v[1] = sp_r[1] = ncol; 323 // Work vectors 324 casadi_int* s = iw; iw += ncol; 325 // Local variables 326 casadi_int r, c, k, k1, top, len, k2, r2; 327 // Clear w to mark nodes 328 for (r=0; r<nrow_ext; ++r) iw[r] = -1; 329 // Number of nonzeros in v and r 330 casadi_int nnz_r=0, nnz_v=0; 331 // Compute V and R 332 for (c=0; c<ncol; ++c) { 333 // R(:,c) starts here 334 r_colind[c] = nnz_r; 335 // V(:, c) starts here 336 v_colind[c] = k1 = nnz_v; 337 // Add V(c,c) to pattern of V 338 iw[c] = c; 339 v_row[nnz_v++] = c; 340 top = ncol; 341 for (k=colind[c]; k<colind[c+1]; ++k) { 342 r = leftmost[row[k]]; // r = min(find(A(r,:)) 343 // Traverse up c 344 for (len=0; iw[r]!=c; r=parent[r]) { 345 s[len++] = r; 346 iw[r] = c; 347 } 348 while (len>0) s[--top] = s[--len]; // push path on stack 349 r = pinv[row[k]]; // r = permuted row of A(:,c) 350 if (r>c && iw[r]<c) { 351 v_row[nnz_v++] = r; // add r to pattern of V(:,c) 352 iw[r] = c; 353 } 354 } 355 // For each r in pattern of R(:,c) 356 for (k = top; k<ncol; ++k) { 357 // R(r,c) is nonzero 358 r = s[k]; 359 // Apply (V(r), beta(r)) to x: x -= v*beta*v'*x 360 r_row[nnz_r++] = r; 361 if (parent[r]==c) { 362 for (k2=v_colind[r]; k2<v_colind[r+1]; ++k2) { 363 r2 = v_row[k2]; 364 if (iw[r2]<c) { 365 iw[r2] = c; 366 v_row[nnz_v++] = r2; 367 } 368 } 369 } 370 } 371 // R(c,c) = norm(x) 372 r_row[nnz_r++] = c; 373 } 374 // Finalize R, V 375 r_colind[ncol] = nnz_r; 376 v_colind[ncol] = nnz_v; 377 } 378 379 void SparsityInternal:: ldl_colind(const casadi_int * sp,casadi_int * parent,casadi_int * l_colind,casadi_int * w)380 ldl_colind(const casadi_int* sp, casadi_int* parent, casadi_int* l_colind, casadi_int* w) { 381 /* Modified version of LDL 382 Copyright(c) Timothy A. Davis, 2005-2013 383 Licensed as a derivative work under the GNU LGPL 384 */ 385 casadi_int n = sp[0]; 386 const casadi_int *colind=sp+2, *row=sp+2+n+1; 387 // Local variables 388 casadi_int r, c, k; 389 // Work vectors 390 casadi_int* visited=w; w+=n; 391 // Loop over columns 392 for (c=0; c<n; ++c) { 393 // L(c,:) pattern: all nodes reachable in etree from nz in A(0:c-1,c) 394 parent[c] = -1; // parent of c is not yet known 395 visited[c] = c; // mark node c as visited 396 l_colind[1+c] = 0; // count of nonzeros in column c of L 397 // Loop over strictly upper triangular entries A 398 for (k=colind[c]; k<colind[c+1] && (r=row[k])<c; ++k) { 399 // Follow path from r to root of etree, stop at visited node 400 while (visited[r]!=c) { 401 // Find parent of r if not yet determined 402 if (parent[r]==-1) parent[r]=c; 403 l_colind[1+r]++; // L(c,r) is nonzero 404 visited[r] = c; // mark r as visited 405 r=parent[r]; // proceed to parent row 406 } 407 } 408 } 409 // Cumsum 410 l_colind[0] = 0; 411 for (c=0; c<n; ++c) l_colind[c+1] += l_colind[c]; 412 } 413 414 void SparsityInternal:: ldl_row(const casadi_int * sp,const casadi_int * parent,casadi_int * l_colind,casadi_int * l_row,casadi_int * w)415 ldl_row(const casadi_int* sp, const casadi_int* parent, casadi_int* l_colind, 416 casadi_int* l_row, casadi_int *w) { 417 /* Modified version of LDL 418 Copyright(c) Timothy A. Davis, 2005-2013 419 Licensed as a derivative work under the GNU LGPL 420 */ 421 // Extract sparsity 422 casadi_int n = sp[0]; 423 const casadi_int *colind = sp+2, *row = sp+n+3; 424 // Work vectors 425 casadi_int *visited=w; w+=n; 426 // Local variables 427 casadi_int r, c, k; 428 // Compute nonzero pattern of kth row of L 429 for (c=0; c<n; ++c) { 430 // Not yet visited 431 visited[c] = c; 432 // Loop over nonzeros in upper triangular half 433 for (k=colind[c]; k<colind[c+1] && (r=row[k])<c; ++k) { 434 // Loop over dependent rows 435 while (visited[r]!=c) { 436 l_row[l_colind[r]++] = c; // L(c,r) is nonzero 437 visited[r] = c; // mark r as visited 438 r=parent[r]; // proceed to parent row 439 } 440 } 441 } 442 // Restore l_colind by shifting it forward 443 k=0; 444 for (c=0; c<n; ++c) { 445 r=l_colind[c]; 446 l_colind[c]=k; 447 k=r; 448 } 449 } 450 451 SparsityInternal:: SparsityInternal(casadi_int nrow,casadi_int ncol,const casadi_int * colind,const casadi_int * row)452 SparsityInternal(casadi_int nrow, casadi_int ncol, 453 const casadi_int* colind, const casadi_int* row) : 454 sp_(2 + ncol+1 + colind[ncol]), btf_(nullptr) { 455 sp_[0] = nrow; 456 sp_[1] = ncol; 457 std::copy(colind, colind+ncol+1, sp_.begin()+2); 458 std::copy(row, row+colind[ncol], sp_.begin()+2+ncol+1); 459 } 460 ~SparsityInternal()461 SparsityInternal::~SparsityInternal() { 462 delete btf_; 463 } 464 btf() const465 const SparsityInternal::Btf& SparsityInternal::btf() const { 466 if (!btf_) { 467 btf_ = new SparsityInternal::Btf(); 468 btf_->nb = btf(btf_->rowperm, btf_->colperm, btf_->rowblock, btf_->colblock, 469 btf_->coarse_rowblock, btf_->coarse_colblock); 470 } 471 return *btf_; 472 } 473 474 numel() const475 casadi_int SparsityInternal::numel() const { 476 return size1()*size2(); 477 } 478 disp(ostream & stream,bool more) const479 void SparsityInternal::disp(ostream &stream, bool more) const { 480 stream << dim(!is_dense()); 481 if (more) { 482 stream << endl; 483 stream << "colind: " << get_colind() << endl; 484 stream << "row: " << get_row() << endl; 485 } 486 } 487 get_col() const488 vector<casadi_int> SparsityInternal::get_col() const { 489 const casadi_int* colind = this->colind(); 490 vector<casadi_int> col(nnz()); 491 for (casadi_int r=0; r<size2(); ++r) { 492 for (casadi_int el = colind[r]; el < colind[r+1]; ++el) { 493 col[el] = r; 494 } 495 } 496 return col; 497 } 498 T() const499 Sparsity SparsityInternal::T() const { 500 // Dummy mapping 501 vector<casadi_int> mapping; 502 503 return transpose(mapping); 504 } 505 transpose(vector<casadi_int> & mapping,bool invert_mapping) const506 Sparsity SparsityInternal::transpose(vector<casadi_int>& mapping, bool invert_mapping) const { 507 // Get the sparsity of the transpose in sparse triplet form 508 vector<casadi_int> trans_col = get_row(); 509 vector<casadi_int> trans_row = get_col(); 510 511 // Create the sparsity pattern 512 return Sparsity::triplet(size2(), size1(), trans_row, trans_col, mapping, invert_mapping); 513 } 514 dfs(casadi_int j,casadi_int top,std::vector<casadi_int> & xi,std::vector<casadi_int> & pstack,const std::vector<casadi_int> & pinv,std::vector<bool> & marked) const515 casadi_int SparsityInternal::dfs(casadi_int j, casadi_int top, std::vector<casadi_int>& xi, 516 std::vector<casadi_int>& pstack, 517 const std::vector<casadi_int>& pinv, 518 std::vector<bool>& marked) const { 519 /* 520 Modified version of cs_dfs in CSparse 521 Copyright(c) Timothy A. Davis, 2006-2009 522 Licensed as a derivative work under the GNU LGPL 523 */ 524 casadi_int head = 0; 525 const casadi_int* colind = this->colind(); 526 const casadi_int* row = this->row(); 527 528 // initialize the recursion stack 529 xi[0] = j; 530 while (head >= 0) { 531 532 // get j from the top of the recursion stack 533 j = xi[head]; 534 casadi_int jnew = !pinv.empty() ? (pinv[j]) : j; 535 if (!marked[j]) { 536 537 // mark node j as visited 538 marked[j]=true; 539 pstack[head] = (jnew < 0) ? 0 : colind[jnew]; 540 } 541 542 // node j done if no unvisited neighbors 543 casadi_int done = 1; 544 casadi_int p2 = (jnew < 0) ? 0 : colind[jnew+1]; 545 546 // examine all neighbors of j 547 for (casadi_int p = pstack[head]; p< p2; ++p) { 548 549 // consider neighbor node i 550 casadi_int i = row[p]; 551 552 // skip visited node i 553 if (marked[i]) continue ; 554 555 // pause depth-first search of node j 556 pstack[head] = p; 557 558 // start dfs at node i 559 xi[++head] = i; 560 561 // node j is not done 562 done = 0; 563 564 // break, to start dfs (i) 565 break; 566 } 567 568 //depth-first search at node j is done 569 if (done) { 570 // remove j from the recursion stack 571 head--; 572 573 // and place in the output stack 574 xi[--top] = j ; 575 } 576 } 577 return (top) ; 578 } 579 scc(std::vector<casadi_int> & p,std::vector<casadi_int> & r) const580 casadi_int SparsityInternal::scc(std::vector<casadi_int>& p, 581 std::vector<casadi_int>& r) const { 582 /* 583 Modified version of cs_scc in CSparse 584 Copyright(c) Timothy A. Davis, 2006-2009 585 Licensed as a derivative work under the GNU LGPL 586 */ 587 vector<casadi_int> tmp; 588 589 Sparsity AT = T(); 590 591 vector<casadi_int> xi(2*size2()+1); 592 vector<casadi_int>& Blk = xi; 593 594 vector<casadi_int> pstack(size2()+1); 595 596 p.resize(size2()); 597 r.resize(size2()+6); 598 599 vector<bool> marked(size2(), false); 600 601 casadi_int top = size2(); 602 603 //first dfs(A) to find finish times (xi) 604 for (casadi_int i = 0; i<size2(); ++i) { 605 if (!marked[i]) 606 top = dfs(i, top, xi, pstack, tmp, marked); 607 } 608 609 //restore A; unmark all nodes 610 fill(marked.begin(), marked.end(), false); 611 612 top = size2(); 613 casadi_int nb = size2(); 614 615 // dfs(A') to find strongly connnected comp 616 for (casadi_int k=0 ; k < size2() ; ++k) { 617 // get i in reverse order of finish times 618 casadi_int i = xi[k]; 619 620 // skip node i if already ordered 621 if (marked[i]) continue; 622 623 // node i is the start of a component in p 624 r[nb--] = top; 625 top = AT.dfs(i, top, p, pstack, tmp, marked); 626 } 627 628 // first block starts at zero; shift r up 629 r[nb] = 0; 630 for (casadi_int k = nb ; k <= size2() ; ++k) 631 r[k-nb] = r[k] ; 632 633 // nb = # of strongly connected components 634 nb = size2()-nb; 635 636 // sort each block in natural order 637 for (casadi_int b = 0 ; b < nb ; b++) { 638 for (casadi_int k = r[b]; k<r[b+1] ; ++k) 639 Blk[p[k]] = b ; 640 } 641 642 // Get p; shift r down (side effect) 643 for (casadi_int i=0; i<size2(); ++i) { 644 p[r[Blk[i]]++] = i; 645 } 646 647 // Shift up r 648 r.resize(nb+1); 649 for (casadi_int i=nb; i>0; --i) { 650 r[i]=r[i-1]; 651 } 652 r[0]=0; 653 654 return nb; 655 } 656 amd() const657 std::vector<casadi_int> SparsityInternal::amd() const { 658 /* 659 Modified version of cs_amd in CSparse 660 Copyright(c) Timothy A. Davis, 2006-2009 661 Licensed as a derivative work under the GNU LGPL 662 */ 663 casadi_assert(is_symmetric(), "AMD requires a symmetric matrix"); 664 // Get sparsity 665 casadi_int n=size2(); 666 vector<casadi_int> colind = get_colind(); 667 vector<casadi_int> row = get_row(); 668 // Drop diagonal entries 669 casadi_int nnz = 0; // number of nonzeros after pruning 670 casadi_int col_begin, col_end=0; 671 for (casadi_int c=0; c<n; ++c) { 672 // Get the range of nonzeros for the column, before pruning 673 col_begin = col_end; 674 col_end = colind[c+1]; 675 // Loop over nonzeros 676 for (casadi_int k=col_begin; k<col_end; ++k) { 677 if (row[k]!=c) { 678 row[nnz++] = row[k]; 679 } 680 } 681 colind[c+1] = nnz; 682 } 683 // dense threshold 684 casadi_int dense = static_cast<casadi_int>(10*sqrt(static_cast<double>(n))); 685 dense = std::max(casadi_int(16), dense); 686 dense = std::min(n-2, dense); 687 // Allocate result 688 vector<casadi_int> P(n+1); 689 // Work vectors 690 vector<casadi_int> len(n+1), nv(n+1), next(n+1), head(n+1), elen(n+1), degree(n+1), 691 w(n+1), hhead(n+1); 692 // Number of elements 693 casadi_int nel = 0; 694 // Minimal degree 695 casadi_int mindeg = 0; 696 // Maximum length of w 697 casadi_int lemax = 0; 698 // Degree 699 casadi_int d; 700 // ? 701 casadi_uint h; 702 // Flip 703 #define FLIP(i) (-(i)-2) 704 // Elbow room 705 //casadi_int t = nnz + nnz/5 + 2*n; 706 // Initialize quotient graph 707 for (casadi_int k = 0; k<n; ++k) len[k] = colind[k+1] - colind[k]; 708 len[n] = 0; 709 casadi_int nzmax = row.size(); 710 for (casadi_int i=0; i<=n; ++i) { 711 head[i] = -1; // degree list i is empty 712 P[i] = -1; 713 next[i] = -1; 714 hhead[i] = -1; // hash list i is empty 715 nv[i] = 1; // node i is just one node 716 w[i] = 1; // node i is alive 717 elen[i] = 0; // Ek of node i is empty 718 degree[i] = len[i]; // degree of node i 719 } 720 casadi_int mark = wclear(0, 0, get_ptr(w), n); // clear w 721 elen[n] = -2; // n is a dead element 722 colind[n] = -1; // n is a root of assembly tree 723 w[n] = 0; // n is a dead element 724 // Initialize degree lists 725 for (casadi_int i = 0; i < n; ++i) { 726 d = degree[i]; 727 if (d == 0) { // node i is empty 728 elen[i] = -2; // element i is dead 729 nel++; 730 colind[i] = -1; // i is a root of assembly tree 731 w[i] = 0; 732 } else if (d > dense) { // node i is dense 733 nv[i] = 0; // absorb i into element n 734 elen[i] = -1; // node i is dead 735 nel++; 736 colind[i] = FLIP(n); 737 nv[n]++; 738 } else { 739 if (head[d] != -1) P[head[d]] = i; 740 next[i] = head[d]; // put node i in degree list d 741 head[d] = i; 742 } 743 } 744 while (nel < n) { // while (selecting pivots) do 745 // Select node of minimum approximate degree 746 casadi_int k; 747 for (k = -1; mindeg < n && (k = head[mindeg]) == -1; mindeg++) {} 748 if (next[k] != -1) P[next[k]] = -1; 749 head[mindeg] = next[k]; // remove k from degree list 750 casadi_int elenk = elen[k]; // elenk = |Ek| 751 casadi_int nvk = nv[k]; // # of nodes k represents 752 nel += nvk; // nv[k] nodes of A eliminated 753 // Garbage collection 754 if (elenk > 0 && nnz + mindeg >= nzmax) { 755 for (casadi_int j = 0; j < n; j++) { 756 casadi_int p; 757 if ((p = colind[j]) >= 0) { // j is a live node or element 758 colind[j] = row[p]; // save first entry of object 759 row[p] = FLIP(j); // first entry is now FLIP(j) 760 } 761 } 762 casadi_int q, p; 763 for (q = 0, p = 0; p < nnz; ) { // scan all of memory 764 casadi_int j; 765 if ((j = FLIP(row[p++])) >= 0) { // found object j 766 row[q] = colind[j]; // restore first entry of object 767 colind[j] = q++; // new pointer to object j 768 for (casadi_int k3 = 0; k3 < len[j]-1; k3++) row[q++] = row[p++]; 769 } 770 } 771 nnz = q; // row[nnz...nzmax-1] now free 772 } 773 // Construct new element 774 casadi_int dk = 0; 775 nv[k] = -nvk; // flag k as in Lk 776 casadi_int p = colind[k]; 777 casadi_int pk1 = (elenk == 0) ? p : nnz; // do in place if elen[k] == 0 778 casadi_int pk2 = pk1; 779 casadi_int e, pj, ln; 780 for (casadi_int k1 = 1; k1 <= elenk + 1; k1++) { 781 if (k1 > elenk) { 782 e = k; // search the nodes in k 783 pj = p; // list of nodes starts at row[pj] 784 ln = len[k] - elenk; // length of list of nodes in k 785 } else { 786 e = row[p++]; // search the nodes in e 787 pj = colind[e]; 788 ln = len[e]; // length of list of nodes in e 789 } 790 for (casadi_int k2 = 1; k2 <= ln; k2++) { 791 casadi_int i = row[pj++]; 792 casadi_int nvi; 793 if ((nvi = nv[i]) <= 0) continue; // node i dead, or seen 794 dk += nvi; // degree[Lk] += size of node i 795 nv[i] = -nvi; // negate nv[i] to denote i in Lk 796 row[pk2++] = i; // place i in Lk 797 if (next[i] != -1) P[next[i]] = P[i]; 798 if (P[i] != -1) { // remove i from degree list 799 next[P[i]] = next[i]; 800 } else { 801 head[degree[i]] = next[i]; 802 } 803 } 804 if (e != k) { 805 colind[e] = FLIP(k); // absorb e into k 806 w[e] = 0; // e is now a dead element 807 } 808 } 809 if (elenk != 0) nnz = pk2; // row[nnz...nzmax] is free 810 degree[k] = dk; // external degree of k - |Lk\i| 811 colind[k] = pk1; // element k is in row[pk1..pk2-1] 812 len[k] = pk2 - pk1; 813 elen[k] = -2; // k is now an element 814 // Find set differences 815 mark = wclear(mark, lemax, get_ptr(w), n); // clear w if necessary 816 for (casadi_int pk = pk1; pk < pk2; pk++) { // scan 1: find |Le\Lk| 817 casadi_int i = row[pk]; 818 casadi_int eln; 819 if ((eln = elen[i]) <= 0) continue; // skip if elen[i] empty 820 casadi_int nvi = -nv[i]; // nv[i] was negated 821 casadi_int wnvi = mark - nvi; 822 for (p = colind[i]; p <= colind[i] + eln - 1; p++) { // scan Ei 823 e = row[p]; 824 if (w[e] >= mark) { 825 w[e] -= nvi; // decrement |Le\Lk| 826 } else if (w[e] != 0) { // ensure e is a live element 827 w[e] = degree[e] + wnvi; /* 1st time e seen in scan 1 */ 828 } 829 } 830 } 831 // Degree update 832 for (casadi_int pk = pk1; pk < pk2; pk++) { // scan2: degree update 833 casadi_int i = row[pk]; // consider node i in Lk 834 casadi_int p1 = colind[i]; 835 casadi_int p2 = p1 + elen[i] - 1; 836 casadi_int pn = p1; 837 for (h = 0, d = 0, p = p1; p <= p2; p++) { // scan Ei 838 e = row[p]; 839 if (w[e] != 0) { // e is an unabsorbed element 840 casadi_int dext = w[e] - mark; // dext = |Le\Lk| 841 if (dext > 0) { 842 d += dext; // sum up the set differences 843 row[pn++] = e; // keep e in Ei 844 h += e; // compute the hash of node i 845 } else { 846 colind[e] = FLIP(k); // aggressive absorb. e->k 847 w[e] = 0; // e is a dead element 848 } 849 } 850 } 851 elen[i] = pn - p1 + 1; // elen[i] = |Ei| 852 casadi_int p3 = pn; 853 casadi_int p4 = p1 + len[i]; 854 for (p = p2 + 1; p < p4; p++) { // prune edges in Ai 855 casadi_int j = row[p]; 856 casadi_int nvj; 857 if ((nvj = nv[j]) <= 0) continue; // node j dead or in Lk 858 d += nvj; // degree(i) += |j| 859 row[pn++] = j; // place j in node list of i 860 h += j; // compute hash for node i 861 } 862 if (d == 0) { // check for mass elimination 863 colind[i] = FLIP(k); // absorb i into k 864 casadi_int nvi = -nv[i]; 865 dk -= nvi; // |Lk| -= |i| 866 nvk += nvi; // |k| += nv[i] 867 nel += nvi; 868 nv[i] = 0; 869 elen[i] = -1; // node i is dead 870 } else { 871 degree[i] = std::min(degree[i], d); // update degree(i) 872 row[pn] = row[p3]; // move first node to end 873 row[p3] = row[p1]; // move 1st el. to end of Ei 874 row[p1] = k; // add k as 1st element in of Ei 875 len[i] = pn - p1 + 1; // new len of adj. list of node i 876 h %= n; // finalize hash of i 877 next[i] = hhead[h]; // place i in hash bucket 878 hhead[h] = i; 879 P[i] = h; // save hash of i in P[i] 880 } 881 } // scan2 is done 882 degree[k] = dk; // finalize |Lk| 883 lemax = std::max(lemax, dk); 884 mark = wclear(mark+lemax, lemax, get_ptr(w), n); // clear w 885 // Supernode detection 886 for (casadi_int pk = pk1; pk < pk2; pk++) { 887 casadi_int i = row[pk]; 888 if (nv[i] >= 0) continue; // skip if i is dead 889 h = P[i]; // scan hash bucket of node i 890 i = hhead[h]; 891 hhead[h] = -1; // hash bucket will be empty 892 for (; i != -1 && next[i] != -1; i = next[i], mark++) { 893 ln = len[i]; 894 casadi_int eln = elen[i]; 895 for (p = colind[i]+1; p <= colind[i] + ln-1; p++) w[row[p]] = mark; 896 casadi_int jlast = i; 897 for (casadi_int j = next[i]; j != -1; ) { // compare i with all j 898 casadi_int ok = (len[j] == ln) && (elen[j] == eln); 899 for (p = colind[j] + 1; ok && p <= colind[j] + ln - 1; p++) { 900 if (w[row[p]] != mark) ok = 0; // compare i and j 901 } 902 if (ok) { // i and j are identical 903 colind[j] = FLIP(i); // absorb j into i 904 nv[i] += nv[j]; 905 nv[j] = 0; 906 elen[j] = -1; // node j is dead 907 j = next[j]; // delete j from hash bucket 908 next[jlast] = j; 909 } else { 910 jlast = j; // j and i are different 911 j = next[j]; 912 } 913 } 914 } 915 } 916 // Finalize new element 917 casadi_int pk; 918 for (p = pk1, pk = pk1; pk < pk2; pk++) { // finalize Lk 919 casadi_int i = row[pk]; 920 casadi_int nvi; 921 if ((nvi = -nv[i]) <= 0) continue; // skip if i is dead 922 nv[i] = nvi; // restore nv[i] 923 d = degree[i] + dk - nvi; // compute external degree(i) 924 d = std::min(d, n - nel - nvi); 925 if (head[d] != -1) P[head[d]] = i; 926 next[i] = head[d]; // put i back in degree list 927 P[i] = -1; 928 head[d] = i; 929 mindeg = std::min(mindeg, d); // find new minimum degree 930 degree[i] = d; 931 row[p++] = i; // place i in Lk 932 } 933 nv[k] = nvk; // # nodes absorbed into k 934 if ((len[k] = p-pk1) == 0) { // length of adj list of element k 935 colind[k] = -1; // k is a root of the tree 936 w[k] = 0; // k is now a dead element 937 } 938 if (elenk != 0) nnz = p; // free unused space in Lk 939 } 940 // Postordering 941 for (casadi_int i = 0; i < n; i++) colind[i] = FLIP(colind[i]); // fix assembly tree 942 for (casadi_int j = 0; j <= n; j++) head[j] = -1; 943 for (casadi_int j = n; j >= 0; j--) { // place unordered nodes in lists 944 if (nv[j] > 0) continue; // skip if j is an element 945 next[j] = head[colind[j]]; // place j in list of its parent 946 head[colind[j]] = j; 947 } 948 for (casadi_int e = n; e >= 0; e--) { // place elements in lists 949 if (nv[e] <= 0) continue; // skip unless e is an element 950 if (colind[e] != -1) { 951 next[e] = head[colind[e]]; // place e in list of its parent 952 head[colind[e]] = e; 953 } 954 } 955 for (casadi_int k = 0, i = 0; i <= n; i++) { // postorder the assembly tree 956 if (colind[i] == -1) k = postorder_dfs(i, k, get_ptr(head), get_ptr(next), 957 get_ptr(P), get_ptr(w)); 958 } 959 P.resize(n); 960 return P; 961 #undef FLIP 962 } 963 bfs(casadi_int n,std::vector<casadi_int> & wi,std::vector<casadi_int> & wj,std::vector<casadi_int> & queue,const std::vector<casadi_int> & imatch,const std::vector<casadi_int> & jmatch,casadi_int mark) const964 void SparsityInternal::bfs(casadi_int n, std::vector<casadi_int>& wi, std::vector<casadi_int>& wj, 965 std::vector<casadi_int>& queue, const std::vector<casadi_int>& imatch, 966 const std::vector<casadi_int>& jmatch, casadi_int mark) const { 967 /* 968 Modified version of cs_bfs in CSparse 969 Copyright(c) Timothy A. Davis, 2006-2009 970 Licensed as a derivative work under the GNU LGPL 971 */ 972 casadi_int head = 0, tail = 0, j, i, p, j2 ; 973 974 // place all unmatched nodes in queue 975 for (j=0; j<n; ++j) { 976 // skip j if matched 977 if (imatch[j] >= 0) continue; 978 979 // j in set C0 (R0 if transpose) 980 wj[j] = 0; 981 982 // place unmatched row j in queue 983 queue[tail++] = j; 984 } 985 986 // quick return if no unmatched nodes 987 if (tail == 0) return; 988 989 Sparsity trans; 990 const casadi_int *C_row, *C_colind; 991 if (mark == 1) { 992 C_row = row(); 993 C_colind = colind(); 994 } else { 995 trans = T(); 996 C_row = trans.row(); 997 C_colind = trans.colind(); 998 } 999 1000 // while queue is not empty 1001 while (head < tail) { 1002 1003 // get the head of the queue 1004 j = queue[head++]; 1005 for (p = C_colind[j] ; p < C_colind[j+1] ; p++) { 1006 i = C_row[p] ; 1007 1008 // skip if i is marked 1009 if (wi[i] >= 0) continue; 1010 1011 // i in set R1 (C3 if transpose) 1012 wi[i] = mark; 1013 1014 // traverse alternating path to j2 1015 j2 = jmatch[i]; 1016 1017 // skip j2 if it is marked 1018 if (wj[j2] >= 0) continue; 1019 1020 // j2 in set C1 (R3 if transpose) 1021 wj[j2] = mark; 1022 1023 // add j2 to queue 1024 queue[tail++] = j2; 1025 } 1026 } 1027 } 1028 matched(casadi_int n,const std::vector<casadi_int> & wj,const std::vector<casadi_int> & imatch,std::vector<casadi_int> & p,std::vector<casadi_int> & q,std::vector<casadi_int> & cc,std::vector<casadi_int> & rr,casadi_int set,casadi_int mark)1029 void SparsityInternal::matched(casadi_int n, const std::vector<casadi_int>& wj, 1030 const std::vector<casadi_int>& imatch, std::vector<casadi_int>& p, 1031 std::vector<casadi_int>& q, std::vector<casadi_int>& cc, std::vector<casadi_int>& rr, 1032 casadi_int set, casadi_int mark) { 1033 /* 1034 Modified version of cs_matched in CSparse 1035 Copyright(c) Timothy A. Davis, 2006-2009 1036 Licensed as a derivative work under the GNU LGPL 1037 */ 1038 casadi_int kc = cc[set]; 1039 casadi_int kr = rr[set-1] ; 1040 for (casadi_int j=0; j<n; ++j) { 1041 // skip if j is not in C set 1042 if (wj[j] != mark) continue; 1043 1044 p[kr++] = imatch[j] ; 1045 q[kc++] = j ; 1046 } 1047 1048 cc[set+1] = kc ; 1049 rr[set] = kr ; 1050 } 1051 unmatched(casadi_int m,const std::vector<casadi_int> & wi,std::vector<casadi_int> & p,std::vector<casadi_int> & rr,casadi_int set)1052 void SparsityInternal::unmatched(casadi_int m, const std::vector<casadi_int>& wi, 1053 std::vector<casadi_int>& p, std::vector<casadi_int>& rr, casadi_int set) { 1054 /* 1055 Modified version of cs_unmatched in CSparse 1056 Copyright(c) Timothy A. Davis, 2006-2009 1057 Licensed as a derivative work under the GNU LGPL 1058 */ 1059 casadi_int i, kr = rr[set] ; 1060 for (i=0; i<m; i++) 1061 if (wi[i] == 0) 1062 p[kr++] = i; 1063 1064 rr[set+1] = kr; 1065 } 1066 rprune(casadi_int i,casadi_int j,double aij,void * other)1067 casadi_int SparsityInternal::rprune(casadi_int i, casadi_int j, double aij, void *other) { 1068 /* 1069 Modified version of cs_rprune in CSparse 1070 Copyright(c) Timothy A. Davis, 2006-2009 1071 Licensed as a derivative work under the GNU LGPL 1072 */ 1073 vector<casadi_int> &rr = *static_cast<vector<casadi_int> *>(other); 1074 return (i >= rr[1] && i < rr[2]) ; 1075 } 1076 augment(casadi_int k,std::vector<casadi_int> & jmatch,casadi_int * cheap,std::vector<casadi_int> & w,casadi_int * js,casadi_int * is,casadi_int * ps) const1077 void SparsityInternal::augment(casadi_int k, std::vector<casadi_int>& jmatch, casadi_int *cheap, 1078 std::vector<casadi_int>& w, casadi_int *js, casadi_int *is, casadi_int *ps) const { 1079 /* 1080 Modified version of cs_augment in CSparse 1081 Copyright(c) Timothy A. Davis, 2006-2009 1082 Licensed as a derivative work under the GNU LGPL 1083 */ 1084 const casadi_int* colind = this->colind(); 1085 const casadi_int* row = this->row(); 1086 1087 casadi_int found = 0, p, i = -1, head = 0, j ; 1088 1089 // start with just node k in jstack 1090 js[0] = k ; 1091 1092 while (head >= 0) { 1093 // --- Start (or continue) depth-first-search at node j ------------- 1094 1095 // get j from top of jstack 1096 j = js[head]; 1097 1098 // 1st time j visited for kth path 1099 if (w[j] != k) { 1100 1101 // mark j as visited for kth path 1102 w[j] = k; 1103 for (p = cheap[j] ; p < colind[j+1] && !found; ++p) { 1104 i = row[p] ; /* try a cheap assignment (i, j) */ 1105 found = (jmatch[i] == -1) ; 1106 } 1107 1108 // start here next time j is traversed 1109 cheap[j] = p; 1110 if (found) { 1111 // row j matched with col i 1112 is[head] = i; 1113 1114 // end of augmenting path 1115 break; 1116 } 1117 1118 // no cheap match: start dfs for j 1119 ps[head] = colind[j]; 1120 } 1121 1122 // --- Depth-first-search of neighbors of j ------------------------- 1123 for (p = ps[head]; p<colind[j+1]; ++p) { 1124 1125 // consider col i 1126 i = row[p]; 1127 1128 // skip jmatch[i] if marked 1129 if (w[jmatch[i]] == k) continue; 1130 1131 // pause dfs of node j 1132 ps[head] = p + 1; 1133 1134 // i will be matched with j if found 1135 is[head] = i; 1136 1137 // start dfs at row jmatch[i] 1138 js[++head] = jmatch[i]; 1139 break ; 1140 } 1141 1142 // node j is done; pop from stack 1143 if (p == colind[j+1]) head--; 1144 } // augment the match if path found: 1145 1146 if (found) 1147 for (p = head; p>=0; --p) 1148 jmatch[is[p]] = js[p]; 1149 } 1150 maxtrans(std::vector<casadi_int> & imatch,std::vector<casadi_int> & jmatch,Sparsity & trans,casadi_int seed) const1151 void SparsityInternal::maxtrans(std::vector<casadi_int>& imatch, std::vector<casadi_int>& jmatch, 1152 Sparsity& trans, casadi_int seed) const { 1153 /* 1154 Modified version of cs_maxtrans in CSparse 1155 Copyright(c) Timothy A. Davis, 2006-2009 1156 Licensed as a derivative work under the GNU LGPL 1157 */ 1158 const casadi_int* colind = this->colind(); 1159 const casadi_int* row = this->row(); 1160 1161 casadi_int n2 = 0, m2 = 0; 1162 1163 // allocate result 1164 jmatch.resize(size1()); 1165 imatch.resize(size2()); 1166 vector<casadi_int> w(size1()+size2()); 1167 1168 // count nonempty columns and rows 1169 casadi_int k=0; 1170 for (casadi_int j=0; j<size2(); ++j) { 1171 n2 += (colind[j] < colind[j+1]); 1172 for (casadi_int p=colind[j]; p < colind[j+1]; ++p) { 1173 w[row[p]] = 1; 1174 1175 // count entries already on diagonal 1176 k += (j == row[p]); 1177 } 1178 } 1179 1180 // quick return if diagonal zero-free 1181 if (k == std::min(size1(), size2())) { 1182 casadi_int i; 1183 for (i=0; i<k; ++i) jmatch[i] = i; 1184 for (; i<size1(); ++i) jmatch[i] = -1; 1185 1186 casadi_int j; 1187 for (j=0; j<k; ++j) imatch[j] = j; 1188 for (; j<size2(); ++j) imatch[j] = -1; 1189 } 1190 1191 for (casadi_int i=0; i<size1(); ++i) m2 += w[i]; 1192 1193 // transpose if needed 1194 if (m2 < n2 && trans.is_null()) 1195 trans = T(); 1196 1197 // Get pointer to sparsity 1198 const SparsityInternal* C = m2 < n2 ? static_cast<const SparsityInternal*>(trans.get()) : this; 1199 const casadi_int* C_colind = C->colind(); 1200 1201 std::vector<casadi_int>& Cjmatch = m2 < n2 ? imatch : jmatch; 1202 std::vector<casadi_int>& Cimatch = m2 < n2 ? jmatch : imatch; 1203 1204 // get workspace 1205 w.resize(5 * C->size2()); 1206 1207 casadi_int *cheap = &w.front() + C->size2(); 1208 casadi_int *js = &w.front() + 2*C->size2(); 1209 casadi_int *is = &w.front() + 3*C->size2(); 1210 casadi_int *ps = &w.front() + 4*C->size2(); 1211 1212 // for cheap assignment 1213 for (casadi_int j=0; j<C->size2(); ++j) 1214 cheap[j] = C_colind[j]; 1215 1216 // all rows unflagged 1217 for (casadi_int j=0; j<C->size2(); ++j) 1218 w[j] = -1; 1219 1220 // nothing matched yet 1221 for (casadi_int i=0; i<C->size1(); ++i) 1222 Cjmatch[i] = -1; 1223 1224 // q = random permutation 1225 std::vector<casadi_int> q = randperm(C->size2(), seed); 1226 1227 // augment, starting at row q[k] 1228 for (k=0; k<C->size2(); ++k) { 1229 C->augment(!q.empty() ? q[k]: k, Cjmatch, cheap, w, js, is, ps); 1230 } 1231 1232 // find col match 1233 for (casadi_int j=0; j<C->size2(); ++j) 1234 Cimatch[j] = -1; 1235 1236 for (casadi_int i = 0; i<C->size1(); ++i) 1237 if (Cjmatch[i] >= 0) 1238 Cimatch[Cjmatch[i]] = i; 1239 } 1240 dmperm(std::vector<casadi_int> & rowperm,std::vector<casadi_int> & colperm,std::vector<casadi_int> & rowblock,std::vector<casadi_int> & colblock,std::vector<casadi_int> & coarse_rowblock,std::vector<casadi_int> & coarse_colblock) const1241 void SparsityInternal::dmperm(std::vector<casadi_int>& rowperm, 1242 std::vector<casadi_int>& colperm, 1243 std::vector<casadi_int>& rowblock, 1244 std::vector<casadi_int>& colblock, 1245 std::vector<casadi_int>& coarse_rowblock, 1246 std::vector<casadi_int>& coarse_colblock) const { 1247 /* 1248 Modified version of cs_dmperm in CSparse 1249 Copyright(c) Timothy A. Davis, 2006-2009 1250 Licensed as a derivative work under the GNU LGPL 1251 */ 1252 casadi_int seed = 0; 1253 1254 // The transpose of the expression 1255 Sparsity trans; 1256 1257 // Part 1: Maximum matching 1258 1259 // col permutation 1260 rowperm.resize(size1()); 1261 1262 // row permutation 1263 colperm.resize(size2()); 1264 1265 // size nb+1, block k is columns r[k] to r[k+1]-1 in A(p, q) 1266 rowblock.resize(size1()+6); 1267 1268 // size nb+1, block k is rows s[k] to s[k+1]-1 in A(p, q) 1269 colblock.resize(size2()+6); 1270 1271 // coarse col decomposition 1272 coarse_rowblock.resize(5); 1273 fill(coarse_rowblock.begin(), coarse_rowblock.end(), 0); 1274 1275 // coarse row decomposition 1276 coarse_colblock.resize(5); 1277 fill(coarse_colblock.begin(), coarse_colblock.end(), 0); 1278 1279 // max transversal 1280 vector<casadi_int> imatch, jmatch; 1281 maxtrans(imatch, jmatch, trans, seed); 1282 1283 // Coarse decomposition 1284 1285 // use rowblock and colblock as workspace 1286 vector<casadi_int>& wi = rowblock; 1287 vector<casadi_int>& wj = colblock; 1288 1289 // unmark all rows for bfs 1290 for (casadi_int j=0; j<size2(); ++j) 1291 wj[j] = -1; 1292 1293 // unmark all columns for bfs 1294 for (casadi_int i=0; i<size1(); ++i) 1295 wi[i] = -1 ; 1296 1297 // find C1, R1 from C0 1298 bfs(size2(), wi, wj, colperm, imatch, jmatch, 1); 1299 1300 // find R3, C3 from R0 1301 bfs(size1(), wj, wi, rowperm, jmatch, imatch, 3); 1302 1303 // unmatched set C0 1304 unmatched(size2(), wj, colperm, coarse_colblock, 0); 1305 1306 // set R1 and C1 1307 matched(size2(), wj, imatch, rowperm, colperm, coarse_colblock, coarse_rowblock, 1, 1); 1308 1309 // set R2 and C2 1310 matched(size2(), wj, imatch, rowperm, colperm, coarse_colblock, coarse_rowblock, 2, -1); 1311 1312 // set R3 and C3 1313 matched(size2(), wj, imatch, rowperm, colperm, coarse_colblock, coarse_rowblock, 3, 3); 1314 1315 // unmatched set R0 1316 unmatched(size1(), wi, rowperm, coarse_rowblock, 3); 1317 1318 // --- Fine decomposition ----------------------------------------------- 1319 // pinv=p' 1320 vector<casadi_int> pinv = invertPermutation(rowperm); 1321 1322 // C=A(p, q) (it will hold A(R2, C2)) 1323 std::vector<casadi_int> colind_C, row_C; 1324 permute(pinv, colperm, 0, colind_C, row_C); 1325 1326 // delete rows C0, C1, and C3 from C 1327 casadi_int nc = coarse_colblock[3] - coarse_colblock[2]; 1328 if (coarse_colblock[2] > 0) { 1329 for (casadi_int j = coarse_colblock[2]; j <= coarse_colblock[3]; ++j) 1330 colind_C[j-coarse_colblock[2]] = colind_C[j]; 1331 } 1332 casadi_int ncol_C = nc; 1333 1334 colind_C.resize(nc+1); 1335 // delete columns R0, R1, and R3 from C 1336 if (coarse_rowblock[2] - coarse_rowblock[1] < size1()) { 1337 drop(rprune, &coarse_rowblock, size1(), ncol_C, colind_C, row_C); 1338 casadi_int cnz = colind_C[nc]; 1339 if (coarse_rowblock[1] > 0) 1340 for (casadi_int k=0; k<cnz; ++k) 1341 row_C[k] -= coarse_rowblock[1]; 1342 } 1343 row_C.resize(colind_C.back()); 1344 casadi_int nrow_C = nc ; 1345 Sparsity C(nrow_C, ncol_C, colind_C, row_C, true); 1346 1347 // find strongly connected components of C 1348 vector<casadi_int> scc_p, scc_r; 1349 casadi_int scc_nb = C.scc(scc_p, scc_r); 1350 1351 // --- Combine coarse and fine decompositions --------------------------- 1352 1353 // C(ps, ps) is the permuted matrix 1354 vector<casadi_int> ps = scc_p; 1355 1356 // kth block is rs[k]..rs[k+1]-1 1357 vector<casadi_int> rs = scc_r; 1358 1359 // # of blocks of A(R2, C2) 1360 casadi_int nb1 = scc_nb; 1361 1362 for (casadi_int k=0; k<nc; ++k) 1363 wj[k] = colperm[ps[k] + coarse_colblock[2]]; 1364 1365 for (casadi_int k=0; k<nc; ++k) 1366 colperm[k + coarse_colblock[2]] = wj[k]; 1367 1368 for (casadi_int k=0; k<nc; ++k) 1369 wi[k] = rowperm[ps[k] + coarse_rowblock[1]]; 1370 1371 for (casadi_int k=0; k<nc; ++k) 1372 rowperm[k + coarse_rowblock[1]] = wi[k]; 1373 1374 // create the fine block partitions 1375 casadi_int nb2 = 0; 1376 rowblock[0] = colblock[0] = 0; 1377 1378 // leading coarse block A (R1, [C0 C1]) 1379 if (coarse_colblock[2] > 0) 1380 nb2++ ; 1381 1382 // coarse block A (R2, C2) 1383 for (casadi_int k=0; k<nb1; ++k) { 1384 // A (R2, C2) splits into nb1 fine blocks 1385 rowblock[nb2] = rs[k] + coarse_rowblock[1]; 1386 colblock[nb2] = rs[k] + coarse_colblock[2] ; 1387 nb2++ ; 1388 } 1389 1390 if (coarse_rowblock[2] < size1()) { 1391 // trailing coarse block A ([R3 R0], C3) 1392 rowblock[nb2] = coarse_rowblock[2]; 1393 colblock[nb2] = coarse_colblock[3]; 1394 nb2++ ; 1395 } 1396 1397 rowblock[nb2] = size1(); 1398 colblock[nb2] = size2() ; 1399 1400 // Shrink rowblock and colblock 1401 rowblock.resize(nb2+1); 1402 colblock.resize(nb2+1); 1403 } 1404 randperm(casadi_int n,casadi_int seed)1405 std::vector<casadi_int> SparsityInternal::randperm(casadi_int n, casadi_int seed) { 1406 /* 1407 Modified version of cs_randperm in CSparse 1408 Copyright(c) Timothy A. Davis, 2006-2009 1409 Licensed as a derivative work under the GNU LGPL 1410 */ 1411 // Return object 1412 std::vector<casadi_int> p; 1413 1414 // return p = empty (identity) 1415 if (seed==0) return p; 1416 1417 // allocate result 1418 p.resize(n); 1419 1420 for (casadi_int k=0; k<n; ++k) 1421 p[k] = n-k-1; 1422 1423 // return reverse permutation 1424 if (seed==-1) return p; 1425 #if defined(_WIN32) 1426 srand(seed); 1427 #else 1428 unsigned int seedu = static_cast<unsigned int>(seed); 1429 #endif 1430 1431 for (casadi_int k=0; k<n; ++k) { 1432 // j = rand casadi_int in range k to n-1 1433 #if defined(_WIN32) 1434 casadi_int j = k + (rand() % (n-k)); // NOLINT(runtime/threadsafe_fn) 1435 #else 1436 casadi_int j = k + (rand_r(&seedu) % (n-k)); 1437 #endif 1438 // swap p[k] and p[j] 1439 casadi_int t = p[j]; 1440 p[j] = p[k]; 1441 p[k] = t; 1442 } 1443 1444 return p; 1445 } 1446 invertPermutation(const std::vector<casadi_int> & p)1447 std::vector<casadi_int> SparsityInternal::invertPermutation(const std::vector<casadi_int>& p) { 1448 vector<casadi_int> pinv(p.size()); 1449 for (casadi_int k=0; k<p.size(); ++k) pinv[p[k]] = k; 1450 return pinv; 1451 } 1452 permute(const std::vector<casadi_int> & pinv,const std::vector<casadi_int> & q,casadi_int values) const1453 Sparsity SparsityInternal::permute(const std::vector<casadi_int>& pinv, 1454 const std::vector<casadi_int>& q, casadi_int values) const { 1455 std::vector<casadi_int> colind_C, row_C; 1456 permute(pinv, q, values, colind_C, row_C); 1457 return Sparsity(size1(), size2(), colind_C, row_C); 1458 } 1459 permute(const std::vector<casadi_int> & pinv,const std::vector<casadi_int> & q,casadi_int values,std::vector<casadi_int> & colind_C,std::vector<casadi_int> & row_C) const1460 void SparsityInternal::permute(const std::vector<casadi_int>& pinv, 1461 const std::vector<casadi_int>& q, casadi_int values, 1462 std::vector<casadi_int>& colind_C, 1463 std::vector<casadi_int>& row_C) const { 1464 /* 1465 Modified version of cs_permute in CSparse 1466 Copyright(c) Timothy A. Davis, 2006-2009 1467 Licensed as a derivative work under the GNU LGPL 1468 */ 1469 const casadi_int* colind = this->colind(); 1470 const casadi_int* row = this->row(); 1471 1472 // alloc column offsets 1473 colind_C.resize(size2()+1); 1474 1475 // Row for each nonzero 1476 row_C.resize(nnz()); 1477 casadi_int nz = 0; 1478 for (casadi_int k = 0; k<size2(); ++k) { 1479 // row k of C is row q[k] of A 1480 colind_C[k] = nz; 1481 1482 casadi_int j = !q.empty() ? (q[k]) : k; 1483 1484 for (casadi_int t = colind[j]; t<colind[j+1]; ++t) { 1485 row_C[nz++] = !pinv.empty() ? (pinv[row[t]]) : row[t] ; 1486 } 1487 } 1488 1489 // finalize the last row of C 1490 colind_C[size2()] = nz; 1491 } 1492 drop(casadi_int (* fkeep)(casadi_int,casadi_int,double,void *),void * other,casadi_int nrow,casadi_int ncol,std::vector<casadi_int> & colind,std::vector<casadi_int> & row)1493 casadi_int SparsityInternal::drop(casadi_int (*fkeep)(casadi_int, casadi_int, double, void *), 1494 void *other, casadi_int nrow, casadi_int ncol, 1495 std::vector<casadi_int>& colind, std::vector<casadi_int>& row) { 1496 /* 1497 Modified version of cs_fkeep in CSparse 1498 Copyright(c) Timothy A. Davis, 2006-2009 1499 Licensed as a derivative work under the GNU LGPL 1500 */ 1501 casadi_int nz = 0; 1502 1503 for (casadi_int j = 0; j<ncol; ++j) { 1504 // get current location of row j 1505 casadi_int p = colind[j]; 1506 1507 // record new location of row j 1508 colind[j] = nz; 1509 for ( ; p < colind[j+1] ; ++p) { 1510 if (fkeep(row[p], j, 1, other)) { 1511 // keep A(i, j) 1512 row[nz++] = row[p] ; 1513 } 1514 } 1515 } 1516 1517 // finalize A 1518 colind[ncol] = nz; 1519 return nz ; 1520 } 1521 wclear(casadi_int mark,casadi_int lemax,casadi_int * w,casadi_int n)1522 casadi_int SparsityInternal::wclear(casadi_int mark, casadi_int lemax, 1523 casadi_int *w, casadi_int n) { 1524 /* 1525 Modified version of cs_wclear in CSparse 1526 Copyright(c) Timothy A. Davis, 2006-2009 1527 Licensed as a derivative work under the GNU LGPL 1528 */ 1529 if (mark < 2 || (mark + lemax < 0)) { 1530 for (casadi_int k = 0; k<n; ++k) if (w[k] != 0) w[k] = 1; 1531 mark = 2 ; 1532 } 1533 // at this point, w [0..n-1] < mark holds 1534 return mark; 1535 } 1536 diag(casadi_int i,casadi_int j,double aij,void * other)1537 casadi_int SparsityInternal::diag(casadi_int i, casadi_int j, double aij, void *other) { 1538 /* 1539 Modified version of cs_diag in CSparse 1540 Copyright(c) Timothy A. Davis, 2006-2009 1541 Licensed as a derivative work under the GNU LGPL 1542 */ 1543 return (i != j) ; 1544 } 1545 scatter(casadi_int j,std::vector<casadi_int> & w,casadi_int mark,casadi_int * Ci,casadi_int nz) const1546 casadi_int SparsityInternal::scatter(casadi_int j, std::vector<casadi_int>& w, 1547 casadi_int mark, casadi_int* Ci, casadi_int nz) const { 1548 /* 1549 Modified version of cs_scatter in CSparse 1550 Copyright(c) Timothy A. Davis, 2006-2009 1551 Licensed as a derivative work under the GNU LGPL 1552 */ 1553 casadi_int i, p; 1554 const casadi_int *Ap = colind(); 1555 const casadi_int *Ai = row(); 1556 1557 for (p = Ap[j]; p<Ap[j+1]; ++p) { 1558 // A(i, j) is nonzero 1559 i = Ai[p]; 1560 1561 if (w[i] < mark) { 1562 // i is new entry in row j 1563 w[i] = mark; 1564 1565 // add i to pattern of C(:, j) 1566 Ci[nz++] = i; 1567 } 1568 } 1569 return nz; 1570 } 1571 multiply(const Sparsity & B) const1572 Sparsity SparsityInternal::multiply(const Sparsity& B) const { 1573 /* 1574 Modified version of cs_multiply in CSparse 1575 Copyright(c) Timothy A. Davis, 2006-2009 1576 Licensed as a derivative work under the GNU LGPL 1577 */ 1578 casadi_int nz = 0; 1579 casadi_assert(size2() == B.size1(), "Dimension mismatch."); 1580 casadi_int m = size1(); 1581 casadi_int anz = nnz(); 1582 casadi_int n = B.size2(); 1583 const casadi_int* Bp = B.colind(); 1584 const casadi_int* Bi = B.row(); 1585 casadi_int bnz = Bp[n]; 1586 1587 // get workspace 1588 vector<casadi_int> w(m); 1589 1590 // allocate result 1591 vector<casadi_int> C_colind(n+1, 0), C_row; 1592 1593 C_colind.resize(anz + bnz); 1594 1595 casadi_int* Cp = &C_colind.front(); 1596 for (casadi_int j=0; j<n; ++j) { 1597 if (nz+m > C_row.size()) { 1598 C_row.resize(2*(C_row.size())+m); 1599 } 1600 1601 // row j of C starts here 1602 Cp[j] = nz; 1603 for (casadi_int p = Bp[j] ; p<Bp[j+1] ; ++p) { 1604 nz = scatter(Bi[p], w, j+1, &C_row.front(), nz); 1605 } 1606 } 1607 1608 // finalize the last row of C 1609 Cp[n] = nz; 1610 C_row.resize(nz); 1611 1612 // Success 1613 return Sparsity(m, n, C_colind, C_row); 1614 } 1615 get_diag(std::vector<casadi_int> & mapping) const1616 Sparsity SparsityInternal::get_diag(std::vector<casadi_int>& mapping) const { 1617 casadi_int nrow = this->size1(); 1618 casadi_int ncol = this->size2(); 1619 const casadi_int* colind = this->colind(); 1620 const casadi_int* row = this->row(); 1621 1622 // Mapping 1623 mapping.clear(); 1624 1625 if (is_vector()) { 1626 // Sparsity pattern 1627 casadi_int n = nrow * ncol; 1628 vector<casadi_int> ret_colind(n+1, 0), ret_row; 1629 1630 // Loop over all entries 1631 casadi_int ret_i=0; 1632 for (casadi_int cc=0; cc<ncol; ++cc) { 1633 for (casadi_int k = colind[cc]; k<colind[cc+1]; ++k) { 1634 casadi_int rr=row[k]; 1635 casadi_int el=rr+nrow*cc; // Corresponding row in the return matrix 1636 while (ret_i<=el) ret_colind[ret_i++]=ret_row.size(); 1637 ret_row.push_back(el); 1638 mapping.push_back(k); 1639 } 1640 } 1641 while (ret_i<=n) ret_colind[ret_i++]=ret_row.size(); 1642 1643 // Construct sparsity pattern 1644 return Sparsity(n, n, ret_colind, ret_row); 1645 1646 } else { 1647 // Sparsity pattern 1648 casadi_int n = std::min(nrow, ncol); 1649 vector<casadi_int> ret_row, ret_colind(2, 0); 1650 1651 // Loop over diagonal nonzeros 1652 for (casadi_int cc=0; cc<n; ++cc) { 1653 for (casadi_int el = colind[cc]; el<colind[cc+1]; ++el) { 1654 if (row[el]==cc) { 1655 ret_row.push_back(row[el]); 1656 ret_colind[1]++; 1657 mapping.push_back(el); 1658 } 1659 } 1660 } 1661 1662 // Construct sparsity pattern 1663 return Sparsity(n, 1, ret_colind, ret_row); 1664 } 1665 } 1666 has_diag() const1667 bool SparsityInternal::has_diag() const { 1668 casadi_int nrow = this->size1(); 1669 casadi_int ncol = this->size2(); 1670 const casadi_int* colind = this->colind(); 1671 const casadi_int* row = this->row(); 1672 for (casadi_int c=0; c<ncol && c<nrow; ++c) { 1673 for (casadi_int k=colind[c]; k<colind[c+1]; ++k) { 1674 if (row[k]==c) return true; 1675 } 1676 } 1677 return false; 1678 } 1679 drop_diag() const1680 Sparsity SparsityInternal::drop_diag() const { 1681 casadi_int nrow = this->size1(); 1682 casadi_int ncol = this->size2(); 1683 const casadi_int* colind = this->colind(); 1684 const casadi_int* row = this->row(); 1685 // Return sparsity 1686 vector<casadi_int> ret_colind(ncol+1), ret_row; 1687 ret_colind[0] = 0; 1688 ret_row.reserve(nnz()); 1689 for (casadi_int c=0; c<ncol; ++c) { 1690 for (casadi_int k=colind[c]; k<colind[c+1]; ++k) { 1691 if (row[k]!=c) { 1692 ret_row.push_back(row[k]); 1693 } 1694 } 1695 ret_colind[c+1] = ret_row.size(); 1696 } 1697 return Sparsity(nrow, ncol, ret_colind, ret_row); 1698 } 1699 dim(bool with_nz) const1700 std::string SparsityInternal::dim(bool with_nz) const { 1701 std::string ret = str(size1()) + "x" + str(size2()); 1702 if (with_nz) ret += "," + str(nnz()) + "nz"; 1703 return ret; 1704 } 1705 repr_el(casadi_int k) const1706 std::string SparsityInternal::repr_el(casadi_int k) const { 1707 casadi_int start_index = GlobalOptions::start_index; 1708 std::stringstream ss; 1709 if (numel()!=nnz()) { 1710 ss << "nonzero index " << k+start_index << " "; 1711 } 1712 casadi_int r = row()[k]; 1713 casadi_int c = get_col()[k]; 1714 ss << "(row " << r+start_index << ", col " << c+start_index << ")"; 1715 1716 return ss.str(); 1717 } 1718 _mtimes(const Sparsity & y) const1719 Sparsity SparsityInternal::_mtimes(const Sparsity& y) const { 1720 // Dimensions of the result 1721 casadi_int d1 = size1(); 1722 casadi_int d2 = y.size2(); 1723 1724 // Elementwise multiplication if one factor is scalar 1725 if (is_scalar(false)) { 1726 return is_dense() ? y : Sparsity(y.size()); 1727 } else if (y.is_scalar(false)) { 1728 return y.is_dense() ? shared_from_this<Sparsity>() : Sparsity(size()); 1729 } 1730 1731 // Quick return if both are dense 1732 if (is_dense() && y.is_dense()) { 1733 return !is_empty() && !y.is_empty() ? Sparsity::dense(d1, d2) : 1734 Sparsity(d1, d2); 1735 } 1736 1737 // Quick return if first factor is diagonal 1738 if (is_diag()) return y; 1739 1740 // Quick return if second factor is diagonal 1741 if (y.is_diag()) return shared_from_this<Sparsity>(); 1742 1743 // Direct access to the vectors 1744 const casadi_int* x_row = row(); 1745 const casadi_int* x_colind = colind(); 1746 const casadi_int* y_row = y.row(); 1747 const casadi_int* y_colind = y.colind(); 1748 1749 // Sparsity pattern of the result 1750 vector<casadi_int> row, col; 1751 1752 // Temporary vector for avoiding duplicate nonzeros 1753 vector<casadi_int> tmp(d1, -1); 1754 1755 // Loop over the nonzeros of y 1756 for (casadi_int cc=0; cc<d2; ++cc) { 1757 for (casadi_int kk=y_colind[cc]; kk<y_colind[cc+1]; ++kk) { 1758 casadi_int rr = y_row[kk]; 1759 1760 // Loop over corresponding columns of x 1761 for (casadi_int kk1=x_colind[rr]; kk1<x_colind[rr+1]; ++kk1) { 1762 casadi_int rr1 = x_row[kk1]; 1763 1764 // Add to pattern if not already encountered 1765 if (tmp[rr1]!=cc) { 1766 tmp[rr1] = cc; 1767 row.push_back(rr1); 1768 col.push_back(cc); 1769 } 1770 } 1771 } 1772 } 1773 1774 // Assemble sparsity pattern and return 1775 return Sparsity::triplet(d1, d2, row, col); 1776 } 1777 is_scalar(bool scalar_and_dense) const1778 bool SparsityInternal::is_scalar(bool scalar_and_dense) const { 1779 return size2()==1 && size1()==1 && (!scalar_and_dense || nnz()==1); 1780 } 1781 is_dense() const1782 bool SparsityInternal::is_dense() const { 1783 return nnz() == numel(); 1784 } 1785 is_row() const1786 bool SparsityInternal::is_row() const { 1787 return size1()==1; 1788 } 1789 is_column() const1790 bool SparsityInternal::is_column() const { 1791 return size2()==1; 1792 } 1793 is_vector() const1794 bool SparsityInternal::is_vector() const { 1795 return is_row() || is_column(); 1796 } 1797 is_empty(bool both) const1798 bool SparsityInternal::is_empty(bool both) const { 1799 return both ? size2()==0 && size1()==0 : size2()==0 || size1()==0; 1800 } 1801 is_diag() const1802 bool SparsityInternal::is_diag() const { 1803 const casadi_int* colind = this->colind(); 1804 const casadi_int* row = this->row(); 1805 1806 // Check if matrix is square 1807 if (size2() != size1()) return false; 1808 1809 // Check if correct number of non-zeros (one per column) 1810 if (nnz() != size2()) return false; 1811 1812 // Check that the row indices are correct 1813 for (casadi_int i=0; i<nnz(); ++i) { 1814 if (row[i]!=i) 1815 return false; 1816 } 1817 1818 // Make sure that the col indices are correct 1819 for (casadi_int i=0; i<size2(); ++i) { 1820 if (colind[i]!=i) 1821 return false; 1822 } 1823 1824 // Diagonal if reached this point 1825 return true; 1826 } 1827 is_square() const1828 bool SparsityInternal::is_square() const { 1829 return size2() == size1(); 1830 } 1831 is_symmetric() const1832 bool SparsityInternal::is_symmetric() const { 1833 return is_transpose(*this); 1834 } 1835 nnz_lower(bool strictly) const1836 casadi_int SparsityInternal::nnz_lower(bool strictly) const { 1837 const casadi_int* colind = this->colind(); 1838 const casadi_int* row = this->row(); 1839 casadi_int nnz = 0; 1840 for (casadi_int cc=0; cc<size2(); ++cc) { 1841 for (casadi_int el = colind[cc]; el<colind[cc+1]; ++el) { 1842 if (cc<row[el] || (!strictly && cc==row[el])) nnz++; 1843 } 1844 } 1845 return nnz; 1846 } 1847 nnz_diag() const1848 casadi_int SparsityInternal::nnz_diag() const { 1849 const casadi_int* colind = this->colind(); 1850 const casadi_int* row = this->row(); 1851 casadi_int nnz = 0; 1852 for (casadi_int cc=0; cc<size2(); ++cc) { 1853 for (casadi_int el = colind[cc]; el < colind[cc+1]; ++el) { 1854 nnz += row[el]==cc; 1855 } 1856 } 1857 return nnz; 1858 } 1859 nnz_upper(bool strictly) const1860 casadi_int SparsityInternal::nnz_upper(bool strictly) const { 1861 const casadi_int* colind = this->colind(); 1862 const casadi_int* row = this->row(); 1863 casadi_int nnz = 0; 1864 for (casadi_int cc=0; cc<size2(); ++cc) { 1865 for (casadi_int el = colind[cc]; el<colind[cc+1]; ++el) { 1866 if (cc>row[el] || (!strictly && cc==row[el])) nnz++; 1867 } 1868 } 1869 return nnz; 1870 } 1871 size() const1872 std::pair<casadi_int, casadi_int> SparsityInternal::size() const { 1873 return std::pair<casadi_int, casadi_int>(size1(), size2()); 1874 } 1875 _erase(const vector<casadi_int> & rr,bool ind1,std::vector<casadi_int> & mapping) const1876 Sparsity SparsityInternal::_erase(const vector<casadi_int>& rr, bool ind1, 1877 std::vector<casadi_int>& mapping) const { 1878 // Quick return if nothing to erase 1879 if (rr.empty()) { 1880 mapping = range(nnz()); 1881 return shared_from_this<Sparsity>(); 1882 } 1883 casadi_assert_in_range(rr, -numel()+ind1, numel()+ind1); 1884 1885 // Handle index-1, negative indices 1886 if (ind1 || has_negative(rr)) { 1887 std::vector<casadi_int> rr_mod = rr; 1888 for (vector<casadi_int>::iterator i=rr_mod.begin(); i!=rr_mod.end(); ++i) { 1889 if (ind1) (*i)--; 1890 if (*i<0) *i += numel(); 1891 } 1892 return _erase(rr_mod, false, mapping); // Call recursively 1893 } 1894 1895 // Sort rr in non-deceasing order, if needed 1896 if (!is_nondecreasing(rr)) { 1897 std::vector<casadi_int> rr_sorted = rr; 1898 std::sort(rr_sorted.begin(), rr_sorted.end()); 1899 return _erase(rr_sorted, false, mapping); 1900 } 1901 1902 // Mapping 1903 mapping.resize(0); 1904 1905 // Quick return if no elements 1906 if (numel()==0) return shared_from_this<Sparsity>(); 1907 1908 // Reserve memory 1909 mapping.reserve(nnz()); 1910 1911 // Number of non-zeros 1912 casadi_int nz=0; 1913 1914 // Elements to be erased 1915 vector<casadi_int>::const_iterator next_rr = rr.begin(); 1916 1917 // Return value 1918 vector<casadi_int> ret_colind = get_colind(), ret_row = get_row(); 1919 1920 // First and last index for the column (note colind_ is being overwritten) 1921 casadi_int k_first, k_last=0; 1922 1923 // Loop over columns 1924 for (casadi_int j=0; j<size2(); ++j) { 1925 // Update k range 1926 k_first = k_last; 1927 k_last = ret_colind[j+1]; 1928 1929 // Loop over nonzeros 1930 for (casadi_int k=k_first; k<k_last; ++k) { 1931 // Get row 1932 casadi_int i=ret_row[k]; 1933 1934 // Corresponding element 1935 casadi_int el = i+j*size1(); 1936 1937 // Continue to the next element to skip 1938 while (next_rr!=rr.end() && *next_rr<el) next_rr++; 1939 1940 // Skip element if necessary 1941 if (next_rr!=rr.end() && *next_rr==el) { 1942 next_rr++; 1943 continue; 1944 } 1945 1946 // Keep element 1947 mapping.push_back(k); 1948 1949 // Update row 1950 ret_row[nz++] = i; 1951 } 1952 1953 // Update colind 1954 ret_colind[j+1] = nz; 1955 } 1956 1957 // Truncate row vector 1958 ret_row.resize(nz); 1959 1960 return Sparsity(size1(), size2(), ret_colind, ret_row); 1961 } 1962 _erase(const vector<casadi_int> & rr,const vector<casadi_int> & cc,bool ind1,std::vector<casadi_int> & mapping) const1963 Sparsity SparsityInternal::_erase(const vector<casadi_int>& rr, const vector<casadi_int>& cc, 1964 bool ind1, std::vector<casadi_int>& mapping) const { 1965 casadi_assert_in_range(rr, -size1()+ind1, size1()+ind1); 1966 casadi_assert_in_range(cc, -size2()+ind1, size2()+ind1); 1967 1968 // Handle index-1, negative indices, non-monotone rr and cc 1969 if (ind1 || has_negative(rr) || has_negative(cc) 1970 || !is_nondecreasing(rr) || !is_nondecreasing(cc)) { 1971 // Create substitute rr 1972 std::vector<casadi_int> rr_mod = rr; 1973 for (vector<casadi_int>::iterator i=rr_mod.begin(); i!=rr_mod.end(); ++i) { 1974 if (ind1) (*i)--; 1975 if (*i<0) *i += size1(); 1976 } 1977 std::sort(rr_mod.begin(), rr_mod.end()); 1978 1979 // Create substitute cc 1980 std::vector<casadi_int> cc_mod = cc; 1981 for (vector<casadi_int>::iterator i=cc_mod.begin(); i!=cc_mod.end(); ++i) { 1982 if (ind1) (*i)--; 1983 if (*i<0) *i += size2(); 1984 } 1985 std::sort(cc_mod.begin(), cc_mod.end()); 1986 1987 // Call recursively 1988 return _erase(rr_mod, cc_mod, false, mapping); 1989 } 1990 1991 // Mapping 1992 mapping.resize(0); 1993 1994 // Quick return if no elements 1995 if (numel()==0) return shared_from_this<Sparsity>(); 1996 1997 // Reserve memory 1998 mapping.reserve(nnz()); 1999 2000 // Return value 2001 vector<casadi_int> ret_colind = get_colind(), ret_row = get_row(); 2002 2003 // Number of non-zeros 2004 casadi_int nz=0; 2005 2006 // Columns to be erased 2007 vector<casadi_int>::const_iterator ie = cc.begin(); 2008 2009 // First and last index for the col 2010 casadi_int el_first=0, el_last=0; 2011 2012 // Loop over columns 2013 for (casadi_int i=0; i<size2(); ++i) { 2014 // Update beginning and end of non-zero indices 2015 el_first = el_last; 2016 el_last = ret_colind[i+1]; 2017 2018 // Is it a col that can be deleted 2019 bool deletable_col = ie!=cc.end() && *ie==i; 2020 if (deletable_col) { 2021 ie++; 2022 2023 // Rows to be erased 2024 vector<casadi_int>::const_iterator je = rr.begin(); 2025 2026 // Loop over nonzero elements of the col 2027 for (casadi_int el=el_first; el<el_last; ++el) { 2028 // Row 2029 casadi_int j=ret_row[el]; 2030 2031 // Continue to the next row to skip 2032 for (; je!=rr.end() && *je<j; ++je) {} 2033 2034 // Remove row if necessary 2035 if (je!=rr.end() && *je==j) { 2036 je++; 2037 continue; 2038 } 2039 2040 // Save old nonzero for each new nonzero 2041 mapping.push_back(el); 2042 2043 // Update row and increase nonzero counter 2044 ret_row[nz++] = j; 2045 } 2046 } else { 2047 // Loop over nonzero elements of the col 2048 for (casadi_int el=el_first; el<el_last; ++el) { 2049 // Row 2050 casadi_int j=ret_row[el]; 2051 2052 // Save old nonzero for each new nonzero 2053 mapping.push_back(el); 2054 2055 // Update row and increase nonzero counter 2056 ret_row[nz++] = j; 2057 } 2058 } 2059 2060 // Register last nonzero of the col 2061 ret_colind[i+1]=nz; 2062 } 2063 2064 // Truncate row matrix 2065 ret_row.resize(nz); 2066 2067 return Sparsity(size1(), size2(), ret_colind, ret_row); 2068 } 2069 get_nz(const vector<casadi_int> & rr,const vector<casadi_int> & cc) const2070 vector<casadi_int> SparsityInternal::get_nz(const vector<casadi_int>& rr, 2071 const vector<casadi_int>& cc) const { 2072 casadi_assert_bounded(rr, size1()); 2073 casadi_assert_bounded(cc, size2()); 2074 2075 std::vector<casadi_int> rr_sorted; 2076 std::vector<casadi_int> rr_sorted_index; 2077 2078 sort(rr, rr_sorted, rr_sorted_index); 2079 2080 vector<casadi_int> ret(cc.size()*rr.size()); 2081 2082 casadi_int stride = rr.size(); 2083 const casadi_int* colind = this->colind(); 2084 const casadi_int* row = this->row(); 2085 2086 for (casadi_int i=0;i<cc.size();++i) { 2087 casadi_int it = cc[i]; 2088 casadi_int el=colind[it]; 2089 for (casadi_int j=0;j<rr_sorted.size();++j) { 2090 casadi_int jt=rr_sorted[j]; 2091 // Continue to the non-zero element 2092 for (; el<colind[it+1] && row[el]<jt; ++el) {} 2093 // Add the non-zero element, if there was an element in the location exists 2094 if (el<colind[it+1] && row[el]== jt) { 2095 ret[i*stride+rr_sorted_index[j]] = el; 2096 } else { 2097 ret[i*stride+rr_sorted_index[j]] = -1; 2098 } 2099 } 2100 } 2101 return ret; 2102 } 2103 sub(const vector<casadi_int> & rr,const SparsityInternal & sp,vector<casadi_int> & mapping,bool ind1) const2104 Sparsity SparsityInternal::sub(const vector<casadi_int>& rr, const SparsityInternal& sp, 2105 vector<casadi_int>& mapping, bool ind1) const { 2106 casadi_assert_dev(rr.size()==sp.nnz()); 2107 2108 // Check bounds 2109 casadi_assert_in_range(rr, -numel()+ind1, numel()+ind1); 2110 2111 // Handle index-1, negative indices 2112 if (ind1 || has_negative(rr)) { 2113 std::vector<casadi_int> rr_mod = rr; 2114 for (vector<casadi_int>::iterator i=rr_mod.begin(); i!=rr_mod.end(); ++i) { 2115 casadi_assert(!(ind1 && (*i)<=0), 2116 "Matlab is 1-based, but requested index " + str(*i) + ". " 2117 "Note that negative slices are disabled in the Matlab interface. " 2118 "Possibly you may want to use 'end'."); 2119 if (ind1) (*i)--; 2120 if (*i<0) *i += numel(); 2121 } 2122 return sub(rr_mod, sp, mapping, false); // Call recursively 2123 } 2124 2125 // Find the nonzeros corresponding to rr 2126 mapping.resize(rr.size()); 2127 std::copy(rr.begin(), rr.end(), mapping.begin()); 2128 get_nz(mapping); 2129 2130 // Construct new pattern of the corresponding elements 2131 vector<casadi_int> ret_colind(sp.size2()+1), ret_row; 2132 ret_colind[0] = 0; 2133 const casadi_int* sp_colind = sp.colind(); 2134 const casadi_int* sp_row = sp.row(); 2135 for (casadi_int c=0; c<sp.size2(); ++c) { 2136 for (casadi_int el=sp_colind[c]; el<sp_colind[c+1]; ++el) { 2137 if (mapping[el]>=0) { 2138 mapping[ret_row.size()] = mapping[el]; 2139 ret_row.push_back(sp_row[el]); 2140 } 2141 } 2142 ret_colind[c+1] = ret_row.size(); 2143 } 2144 mapping.resize(ret_row.size()); 2145 return Sparsity(sp.size1(), sp.size2(), ret_colind, ret_row); 2146 } 2147 sub(const vector<casadi_int> & rr,const vector<casadi_int> & cc,vector<casadi_int> & mapping,bool ind1) const2148 Sparsity SparsityInternal::sub(const vector<casadi_int>& rr, const vector<casadi_int>& cc, 2149 vector<casadi_int>& mapping, bool ind1) const { 2150 casadi_assert_in_range(rr, -size1()+ind1, size1()+ind1); 2151 casadi_assert_in_range(cc, -size2()+ind1, size2()+ind1); 2152 2153 // Handle index-1, negative indices in rr 2154 std::vector<casadi_int> tmp = rr; 2155 for (vector<casadi_int>::iterator i=tmp.begin(); i!=tmp.end(); ++i) { 2156 if (ind1) (*i)--; 2157 if (*i<0) *i += size1(); 2158 } 2159 std::vector<casadi_int> rr_sorted, rr_sorted_index; 2160 sort(tmp, rr_sorted, rr_sorted_index, false); 2161 2162 // Handle index-1, negative indices in cc 2163 tmp = cc; 2164 for (vector<casadi_int>::iterator i=tmp.begin(); i!=tmp.end(); ++i) { 2165 if (ind1) (*i)--; 2166 if (*i<0) *i += size2(); 2167 } 2168 std::vector<casadi_int> cc_sorted, cc_sorted_index; 2169 sort(tmp, cc_sorted, cc_sorted_index, false); 2170 vector<casadi_int> columns, rows; 2171 2172 // With lookup vector 2173 bool with_lookup = static_cast<double>(cc.size())*static_cast<double>(rr.size()) > nnz(); 2174 std::vector<casadi_int> rrlookup; 2175 if (with_lookup) { 2176 // Time complexity: O(ii.size()*(nnz per column)) 2177 // Typical use case: 2178 // a = SX::sym("a", sp_diag(50000)) 2179 // a[:, :] 2180 rrlookup = lookupvector(rr_sorted, size1()); 2181 // Else: Time complexity: O(ii.size()*jj.size()) 2182 // Typical use case: 2183 // a = DM.ones(1000, 1000) 2184 // a[[0, 1],[0, 1]] 2185 } 2186 2187 // count the number of non-zeros 2188 casadi_int nnz = 0; 2189 2190 // loop over the columns of the slice 2191 const casadi_int* colind = this->colind(); 2192 const casadi_int* row = this->row(); 2193 for (casadi_int i=0; i<cc.size(); ++i) { 2194 casadi_int it = cc_sorted[i]; 2195 if (with_lookup) { 2196 // loop over the non-zeros of the matrix 2197 for (casadi_int el=colind[it]; el<colind[it+1]; ++el) { 2198 casadi_int j = row[el]; 2199 casadi_int ji = rrlookup[j]; 2200 if (ji!=-1) { 2201 casadi_int jv = rr_sorted[ji]; 2202 while (ji>=0 && jv == rr_sorted[ji--]) nnz++; 2203 } 2204 } 2205 } else { 2206 // Loop over rr 2207 casadi_int el = colind[it]; 2208 for (casadi_int j=0; j<rr_sorted.size(); ++j) { 2209 casadi_int jt=rr_sorted[j]; 2210 // Continue to the non-zero element 2211 while (el<colind[it+1] && row[el]<jt) el++; 2212 // Add the non-zero element, if there was an element in the location exists 2213 if (el<colind[it+1] && row[el]== jt) nnz++; 2214 } 2215 } 2216 } 2217 2218 mapping.resize(nnz); 2219 columns.resize(nnz); 2220 rows.resize(nnz); 2221 2222 casadi_int k = 0; 2223 // loop over the columns of the slice 2224 for (casadi_int i=0; i<cc.size(); ++i) { 2225 casadi_int it = cc_sorted[i]; 2226 if (with_lookup) { 2227 // loop over the non-zeros of the matrix 2228 for (casadi_int el=colind[it]; el<colind[it+1]; ++el) { 2229 casadi_int jt = row[el]; 2230 casadi_int ji = rrlookup[jt]; 2231 if (ji!=-1) { 2232 casadi_int jv = rr_sorted[ji]; 2233 while (ji>=0 && jv == rr_sorted[ji]) { 2234 rows[k] = rr_sorted_index[ji]; 2235 columns[k] = cc_sorted_index[i]; 2236 mapping[k] = el; 2237 k++; 2238 ji--; 2239 } 2240 } 2241 } 2242 } else { 2243 // Loop over rr 2244 casadi_int el = colind[it]; 2245 for (casadi_int j=0; j<rr_sorted.size(); ++j) { 2246 casadi_int jt=rr_sorted[j]; 2247 // Continue to the non-zero element 2248 while (el<colind[it+1] && row[el]<jt) el++; 2249 // Add the non-zero element, if there was an element in the location exists 2250 if (el<colind[it+1] && row[el]== jt) { 2251 rows[k] = rr_sorted_index[j]; 2252 columns[k] = cc_sorted_index[i]; 2253 mapping[k] = el; 2254 k++; 2255 } 2256 } 2257 } 2258 } 2259 2260 std::vector<casadi_int> sp_mapping; 2261 std::vector<casadi_int> mapping_ = mapping; 2262 Sparsity ret = Sparsity::triplet(rr.size(), cc.size(), rows, columns, sp_mapping, false); 2263 2264 for (casadi_int i=0; i<mapping.size(); ++i) 2265 mapping[i] = mapping_[sp_mapping[i]]; 2266 2267 // Create sparsity pattern 2268 return ret; 2269 } 2270 combine(const Sparsity & y,bool f0x_is_zero,bool function0_is_zero) const2271 Sparsity SparsityInternal::combine(const Sparsity& y, bool f0x_is_zero, 2272 bool function0_is_zero) const { 2273 static vector<unsigned char> mapping; 2274 return combineGen1<false>(y, f0x_is_zero, function0_is_zero, mapping); 2275 } 2276 combine(const Sparsity & y,bool f0x_is_zero,bool function0_is_zero,vector<unsigned char> & mapping) const2277 Sparsity SparsityInternal::combine(const Sparsity& y, bool f0x_is_zero, 2278 bool function0_is_zero, 2279 vector<unsigned char>& mapping) const { 2280 return combineGen1<true>(y, f0x_is_zero, function0_is_zero, mapping); 2281 } 2282 is_subset(const Sparsity & rhs) const2283 bool SparsityInternal::is_subset(const Sparsity& rhs) const { 2284 if (is_equal(rhs)) return true; 2285 std::vector<unsigned char> mapping; 2286 shared_from_this<Sparsity>().unite(rhs, mapping); 2287 for (auto e : mapping) { 2288 if (e==1) return false; 2289 } 2290 return true; 2291 } 2292 2293 template<bool with_mapping> combineGen1(const Sparsity & y,bool f0x_is_zero,bool function0_is_zero,std::vector<unsigned char> & mapping) const2294 Sparsity SparsityInternal::combineGen1(const Sparsity& y, bool f0x_is_zero, 2295 bool function0_is_zero, 2296 std::vector<unsigned char>& mapping) const { 2297 2298 // Quick return if identical 2299 if (is_equal(y)) { 2300 if (with_mapping) { 2301 mapping.resize(y.nnz()); 2302 fill(mapping.begin(), mapping.end(), 1 | 2); 2303 } 2304 return y; 2305 } 2306 2307 if (f0x_is_zero) { 2308 if (function0_is_zero) { 2309 return combineGen<with_mapping, true, true>(y, mapping); 2310 } else { 2311 return combineGen<with_mapping, true, false>(y, mapping); 2312 } 2313 } else if (function0_is_zero) { 2314 return combineGen<with_mapping, false, true>(y, mapping); 2315 } else { 2316 return combineGen<with_mapping, false, false>(y, mapping); 2317 } 2318 } 2319 2320 template<bool with_mapping, bool f0x_is_zero, bool function0_is_zero> combineGen(const Sparsity & y,vector<unsigned char> & mapping) const2321 Sparsity SparsityInternal::combineGen(const Sparsity& y, 2322 vector<unsigned char>& mapping) const { 2323 2324 // Assert dimensions 2325 casadi_assert(size2()==y.size2() && size1()==y.size1(), 2326 "Dimension mismatch : " + str(size()) + " versus " + str(y.size()) + "."); 2327 2328 // Sparsity pattern of the argument 2329 const casadi_int* y_colind = y.colind(); 2330 const casadi_int* y_row = y.row(); 2331 const casadi_int* colind = this->colind(); 2332 const casadi_int* row = this->row(); 2333 2334 // Sparsity pattern of the result 2335 vector<casadi_int> ret_colind(size2()+1, 0); 2336 vector<casadi_int> ret_row; 2337 2338 // Clear the mapping 2339 if (with_mapping) mapping.clear(); 2340 2341 // Loop over columns of both patterns 2342 for (casadi_int i=0; i<size2(); ++i) { 2343 // Non-zero element of the two matrices 2344 casadi_int el1 = colind[i]; 2345 casadi_int el2 = y_colind[i]; 2346 2347 // End of the non-zero elements of the col for the two matrices 2348 casadi_int el1_last = colind[i+1]; 2349 casadi_int el2_last = y_colind[i+1]; 2350 2351 // Loop over the non-zeros of both matrices 2352 while (el1<el1_last || el2<el2_last) { 2353 // Get the rows 2354 casadi_int row1 = el1<el1_last ? row[el1] : size1(); 2355 casadi_int row2 = el2<el2_last ? y_row[el2] : size1(); 2356 2357 // Add to the return matrix 2358 if (row1==row2) { // both nonzero 2359 ret_row.push_back(row1); 2360 if (with_mapping) mapping.push_back( 1 | 2); 2361 el1++; el2++; 2362 } else if (row1<row2) { // only first argument is nonzero 2363 if (!function0_is_zero) { 2364 ret_row.push_back(row1); 2365 if (with_mapping) mapping.push_back(1); 2366 } else { 2367 if (with_mapping) mapping.push_back(1 | 4); 2368 } 2369 el1++; 2370 } else { // only second argument is nonzero 2371 if (!f0x_is_zero) { 2372 ret_row.push_back(row2); 2373 if (with_mapping) mapping.push_back(2); 2374 } else { 2375 if (with_mapping) mapping.push_back(2 | 4); 2376 } 2377 el2++; 2378 } 2379 } 2380 2381 // Save the index of the last nonzero on the col 2382 ret_colind[i+1] = ret_row.size(); 2383 } 2384 2385 // Return cached object 2386 return Sparsity(size1(), size2(), ret_colind, ret_row); 2387 } 2388 is_stacked(const Sparsity & y,casadi_int n) const2389 bool SparsityInternal::is_stacked(const Sparsity& y, casadi_int n) const { 2390 // Quick true if the objects are equal 2391 if (n==1 && is_equal(y)) return true; 2392 // Get sparsity patterns 2393 casadi_int size1 = this->size1(); 2394 casadi_int size2 = this->size2(); 2395 const casadi_int* colind = this->colind(); 2396 const casadi_int* row = this->row(); 2397 casadi_int y_size1 = y.size1(); 2398 casadi_int y_size2 = y.size2(); 2399 const casadi_int* y_colind = y.colind(); 2400 const casadi_int* y_row = y.row(); 2401 // Make sure dimensions are consistent 2402 if (size1!=y_size1 || size2!=n*y_size2) return false; 2403 // Make sure number of nonzeros are consistent 2404 casadi_int nnz = colind[size2], y_nnz = y_colind[y_size2]; 2405 if (nnz!=n*y_nnz) return false; 2406 // Quick return if dense 2407 if (y_nnz==y_size1*y_size2) return true; 2408 // Offset 2409 casadi_int offset = 0; 2410 // Skip the initial zero 2411 colind++; 2412 // For all repeats 2413 for (int i=0; i<n; ++i) { 2414 // Compare column offsets 2415 for (int c=0; c<y_size2; ++c) if (y_colind[c+1]+offset != *colind++) return false; 2416 // Compare row indices 2417 for (int k=0; k<y_nnz; ++k) if (y_row[k] != *row++) return false; 2418 // Update nonzero offset 2419 offset += y_nnz; 2420 } 2421 // Equal if reached this point 2422 return true; 2423 } 2424 is_equal(const Sparsity & y) const2425 bool SparsityInternal::is_equal(const Sparsity& y) const { 2426 // Quick true if the objects are the same 2427 if (this == y.get()) return true; 2428 2429 // Otherwise, compare the patterns 2430 return is_equal(y.size1(), y.size2(), y.colind(), y.row()); 2431 } 2432 pattern_inverse() const2433 Sparsity SparsityInternal::pattern_inverse() const { 2434 // Quick return clauses 2435 if (is_empty()) return Sparsity::dense(size1(), size2()); 2436 if (is_dense()) return Sparsity(size1(), size2()); 2437 2438 // Sparsity of the result 2439 std::vector<casadi_int> row_ret; 2440 std::vector<casadi_int> colind_ret=get_colind(); 2441 const casadi_int* colind = this->colind(); 2442 const casadi_int* row = this->row(); 2443 2444 // Loop over columns 2445 for (casadi_int i=0;i<size2();++i) { 2446 // Update colind vector of the result 2447 colind_ret[i+1]=colind_ret[i]+size1()-(colind[i+1]-colind[i]); 2448 2449 // Counter of new row indices 2450 casadi_int j=0; 2451 2452 // Loop over all nonzeros 2453 for (casadi_int k=colind[i];k<colind[i+1];++k) { 2454 2455 // Try to reach current nonzero 2456 while (j<row[k]) { 2457 // And meanwhile, add nonzeros to the result 2458 row_ret.push_back(j); 2459 j++; 2460 } 2461 j++; 2462 } 2463 // Process the remainder up to the row size 2464 while (j < size1()) { 2465 row_ret.push_back(j); 2466 j++; 2467 } 2468 } 2469 2470 // Return result 2471 return Sparsity(size1(), size2(), colind_ret, row_ret); 2472 } 2473 2474 is_equal(casadi_int y_nrow,casadi_int y_ncol,const std::vector<casadi_int> & y_colind,const std::vector<casadi_int> & y_row) const2475 bool SparsityInternal::is_equal(casadi_int y_nrow, casadi_int y_ncol, 2476 const std::vector<casadi_int>& y_colind, 2477 const std::vector<casadi_int>& y_row) const { 2478 casadi_assert_dev(y_colind.size()==y_ncol+1); 2479 casadi_assert_dev(y_row.size()==y_colind.back()); 2480 return is_equal(y_nrow, y_ncol, get_ptr(y_colind), get_ptr(y_row)); 2481 } 2482 is_equal(casadi_int y_nrow,casadi_int y_ncol,const casadi_int * y_colind,const casadi_int * y_row) const2483 bool SparsityInternal::is_equal(casadi_int y_nrow, casadi_int y_ncol, 2484 const casadi_int* y_colind, const casadi_int* y_row) const { 2485 const casadi_int* colind = this->colind(); 2486 const casadi_int* row = this->row(); 2487 2488 // Get number of nonzeros 2489 casadi_int nz = y_colind[y_ncol]; 2490 2491 // First check dimensions and number of non-zeros 2492 if (nnz()!=nz || size2()!=y_ncol || size1()!=y_nrow) return false; 2493 2494 // Check if dense 2495 if (nnz()==numel()) return true; 2496 2497 // Check the number of non-zeros per col 2498 if (!equal(colind, colind+size2()+1, y_colind)) return false; 2499 2500 // Finally check the row indices 2501 if (!equal(row, row+nz, y_row)) return false; 2502 2503 // Equal if reached this point 2504 return true; 2505 } 2506 _appendVector(const SparsityInternal & sp) const2507 Sparsity SparsityInternal::_appendVector(const SparsityInternal& sp) const { 2508 casadi_assert(size2() == 1 && sp.size2() == 1, 2509 "_appendVector(sp): Both arguments must be vectors but got " 2510 + str(size2()) + " columns for lhs, and " + str(sp.size2()) + " columns for rhs."); 2511 2512 // Get current number of non-zeros 2513 casadi_int sz = nnz(); 2514 2515 // Add row indices 2516 vector<casadi_int> new_row = get_row(); 2517 const casadi_int* sp_row = sp.row(); 2518 new_row.resize(sz + sp.nnz()); 2519 for (casadi_int i=sz; i<new_row.size(); ++i) 2520 new_row[i] = sp_row[i-sz] + size1(); 2521 2522 // New column indices 2523 vector<casadi_int> new_colind(2, 0); 2524 new_colind[1] = new_row.size(); 2525 return Sparsity(size1()+sp.size1(), 1, new_colind, new_row); 2526 } 2527 _appendColumns(const SparsityInternal & sp) const2528 Sparsity SparsityInternal::_appendColumns(const SparsityInternal& sp) const { 2529 casadi_assert(size1()== sp.size1(), 2530 "_appendColumns(sp): row sizes must match but got " + str(size1()) 2531 + " for lhs, and " + str(sp.size1()) + " for rhs."); 2532 2533 // Append rows 2534 vector<casadi_int> new_row = get_row(); 2535 const casadi_int* sp_row = sp.row(); 2536 new_row.insert(new_row.end(), sp_row, sp_row+sp.nnz()); 2537 2538 // Get column indices 2539 vector<casadi_int> new_colind = get_colind(); 2540 const casadi_int* sp_colind = sp.colind(); 2541 new_colind.resize(size2() + sp.size2() + 1); 2542 for (casadi_int i = size2()+1; i<new_colind.size(); ++i) 2543 new_colind[i] = sp_colind[i-size2()] + nnz(); 2544 2545 return Sparsity(size1(), size2()+sp.size2(), new_colind, new_row); 2546 } 2547 _enlargeColumns(casadi_int ncol,const std::vector<casadi_int> & cc,bool ind1) const2548 Sparsity SparsityInternal::_enlargeColumns(casadi_int ncol, const std::vector<casadi_int>& cc, 2549 bool ind1) const { 2550 casadi_assert_in_range(cc, -ncol+ind1, ncol+ind1); 2551 2552 // Handle index-1, negative indices 2553 if (ind1 || has_negative(cc)) { 2554 std::vector<casadi_int> cc_mod = cc; 2555 for (vector<casadi_int>::iterator i=cc_mod.begin(); i!=cc_mod.end(); ++i) { 2556 if (ind1) (*i)--; 2557 if (*i<0) *i += ncol; 2558 } 2559 return _enlargeColumns(ncol, cc_mod, false); // Call recursively 2560 } 2561 2562 // Sparsify the columns 2563 vector<casadi_int> new_colind = get_colind(); 2564 new_colind.resize(ncol+1, nnz()); 2565 2566 casadi_int ik=cc.back(); // need only to update from the last new index 2567 casadi_int nz=nnz(); // number of nonzeros up till this column 2568 for (casadi_int i=cc.size()-1; i>=0; --i) { 2569 // Update colindex for new columns 2570 for (; ik>cc[i]; --ik) { 2571 new_colind[ik] = nz; 2572 } 2573 2574 // Update non-zero counter 2575 nz = new_colind[i]; 2576 2577 // Update colindex for old colums 2578 new_colind[cc[i]] = nz; 2579 } 2580 2581 // Append zeros to the beginning 2582 for (; ik>=0; --ik) { 2583 new_colind[ik] = 0; 2584 } 2585 return Sparsity(size1(), ncol, new_colind, get_row()); 2586 } 2587 _enlargeRows(casadi_int nrow,const std::vector<casadi_int> & rr,bool ind1) const2588 Sparsity SparsityInternal::_enlargeRows(casadi_int nrow, 2589 const std::vector<casadi_int>& rr, bool ind1) const { 2590 casadi_assert_in_range(rr, -nrow+ind1, nrow+ind1); 2591 2592 // Handle index-1, negative indices 2593 if (ind1 || has_negative(rr)) { 2594 std::vector<casadi_int> rr_mod = rr; 2595 for (vector<casadi_int>::iterator i=rr_mod.begin(); i!=rr_mod.end(); ++i) { 2596 if (ind1) (*i)--; 2597 if (*i<0) *i += nrow; 2598 } 2599 return _enlargeRows(nrow, rr_mod, false); // Call recursively 2600 } 2601 2602 // Assert dimensions 2603 casadi_assert_dev(rr.size() == size1()); 2604 2605 // Begin by sparsify the rows 2606 vector<casadi_int> new_row = get_row(); 2607 for (casadi_int k=0; k<nnz(); ++k) { 2608 new_row[k] = rr[new_row[k]]; 2609 } 2610 return Sparsity(nrow, size2(), get_colind(), new_row); 2611 } 2612 makeDense(std::vector<casadi_int> & mapping) const2613 Sparsity SparsityInternal::makeDense(std::vector<casadi_int>& mapping) const { 2614 const casadi_int* colind = this->colind(); 2615 const casadi_int* row = this->row(); 2616 mapping.resize(nnz()); 2617 for (casadi_int i=0; i<size2(); ++i) { 2618 for (casadi_int el=colind[i]; el<colind[i+1]; ++el) { 2619 casadi_int j = row[el]; 2620 mapping[el] = j + i*size1(); 2621 } 2622 } 2623 2624 return Sparsity::dense(size1(), size2()); 2625 } 2626 get_nz(casadi_int rr,casadi_int cc) const2627 casadi_int SparsityInternal::get_nz(casadi_int rr, casadi_int cc) const { 2628 // If negative index, count from the back 2629 if (rr<0) rr += size1(); 2630 if (cc<0) cc += size2(); 2631 const casadi_int* colind = this->colind(); 2632 const casadi_int* row = this->row(); 2633 2634 // Check consistency 2635 casadi_assert(rr>=0 && rr<size1(), "Row index " + str(rr) 2636 + " out of bounds [0, " + str(size1()) + ")"); 2637 casadi_assert(cc>=0 && cc<size2(), "Column index " + str(cc) 2638 + " out of bounds [0, " + str(size2()) + ")"); 2639 2640 // Quick return if matrix is dense 2641 if (is_dense()) return rr+cc*size1(); 2642 2643 // Quick return if past the end 2644 if (colind[cc]==nnz() || (colind[cc+1]==nnz() && row[nnz()-1]<rr)) return -1; 2645 2646 // Find sparse element 2647 for (casadi_int ind=colind[cc]; ind<colind[cc+1]; ++ind) { 2648 if (row[ind] == rr) { 2649 return ind; // element exists 2650 } else if (row[ind] > rr) { 2651 break; // break at the place where the element should be added 2652 } 2653 } 2654 return -1; 2655 } 2656 _reshape(casadi_int nrow,casadi_int ncol) const2657 Sparsity SparsityInternal::_reshape(casadi_int nrow, casadi_int ncol) const { 2658 // If a dimension is negative, call recursively 2659 if (nrow<0 && ncol>0) { 2660 return _reshape(numel()/ncol, ncol); 2661 } else if (nrow>0 && ncol<0) { 2662 return _reshape(nrow, numel()/nrow); 2663 } 2664 2665 casadi_assert(numel() == nrow*ncol, 2666 "reshape: number of elements must remain the same. Old shape is " 2667 + dim() + ". New shape is " + str(nrow) + "x" + str(ncol) 2668 + "=" + str(nrow*ncol) + "."); 2669 std::vector<casadi_int> ret_col(nnz()); 2670 std::vector<casadi_int> ret_row(nnz()); 2671 const casadi_int* colind = this->colind(); 2672 const casadi_int* row = this->row(); 2673 for (casadi_int i=0; i<size2(); ++i) { 2674 for (casadi_int el=colind[i]; el<colind[i+1]; ++el) { 2675 casadi_int j = row[el]; 2676 2677 // Element number 2678 casadi_int k_ret = j+i*size1(); 2679 2680 // Col and row in the new matrix 2681 casadi_int i_ret = k_ret/nrow; 2682 casadi_int j_ret = k_ret%nrow; 2683 ret_col[el] = i_ret; 2684 ret_row[el] = j_ret; 2685 } 2686 } 2687 return Sparsity::triplet(nrow, ncol, ret_row, ret_col); 2688 } 2689 _resize(casadi_int nrow,casadi_int ncol) const2690 Sparsity SparsityInternal::_resize(casadi_int nrow, casadi_int ncol) const { 2691 // Col and row index of the new 2692 vector<casadi_int> row_new, colind_new(ncol+1, 0); 2693 const casadi_int* colind = this->colind(); 2694 const casadi_int* row = this->row(); 2695 2696 // Loop over the columns which may contain nonzeros 2697 casadi_int i; 2698 for (i=0; i<size2() && i<ncol; ++i) { 2699 // First nonzero element of the col 2700 colind_new[i] = row_new.size(); 2701 2702 // Record rows of the nonzeros 2703 for (casadi_int el=colind[i]; el<colind[i+1] && row[el]<nrow; ++el) { 2704 row_new.push_back(row[el]); 2705 } 2706 } 2707 2708 // Save col-indices for the rest of the columns 2709 for (; i<ncol+1; ++i) { 2710 colind_new[i] = row_new.size(); 2711 } 2712 2713 return Sparsity(nrow, ncol, colind_new, row_new); 2714 } 2715 rowsSequential(bool strictly) const2716 bool SparsityInternal::rowsSequential(bool strictly) const { 2717 const casadi_int* colind = this->colind(); 2718 const casadi_int* row = this->row(); 2719 for (casadi_int i=0; i<size2(); ++i) { 2720 casadi_int lastrow = -1; 2721 for (casadi_int k=colind[i]; k<colind[i+1]; ++k) { 2722 2723 // check if not in sequence 2724 if (row[k] < lastrow) 2725 return false; 2726 2727 // Check if duplicate 2728 if (strictly && row[k] == lastrow) 2729 return false; 2730 2731 // update last row of the col 2732 lastrow = row[k]; 2733 } 2734 } 2735 2736 // sequential if reached this point 2737 return true; 2738 } 2739 _removeDuplicates(std::vector<casadi_int> & mapping) const2740 Sparsity SparsityInternal::_removeDuplicates(std::vector<casadi_int>& mapping) const { 2741 casadi_assert_dev(mapping.size()==nnz()); 2742 2743 // Return value (to be hashed) 2744 vector<casadi_int> ret_colind = get_colind(), ret_row = get_row(); 2745 2746 // Nonzero counter without duplicates 2747 casadi_int k_strict=0; 2748 2749 // Loop over columns 2750 for (casadi_int i=0; i<size2(); ++i) { 2751 2752 // Last row encountered on the col so far 2753 casadi_int lastrow = -1; 2754 2755 // Save new col offset (cannot set it yet, since we will need the old value below) 2756 casadi_int new_colind = k_strict; 2757 2758 // Loop over nonzeros (including duplicates) 2759 for (casadi_int k=ret_colind[i]; k<ret_colind[i+1]; ++k) { 2760 2761 // Make sure that the rows appear sequentially 2762 casadi_assert(ret_row[k] >= lastrow, "rows are not sequential"); 2763 2764 // Skip if duplicate 2765 if (ret_row[k] == lastrow) continue; 2766 2767 // update last row encounterd on the col 2768 lastrow = ret_row[k]; 2769 2770 // Update mapping 2771 mapping[k_strict] = mapping[k]; 2772 2773 // Update row index 2774 ret_row[k_strict] = ret_row[k]; 2775 2776 // Increase the strict nonzero counter 2777 k_strict++; 2778 } 2779 2780 // Update col offset 2781 ret_colind[i] = new_colind; 2782 } 2783 2784 // Finalize the sparsity pattern 2785 ret_colind[size2()] = k_strict; 2786 ret_row.resize(k_strict); 2787 mapping.resize(k_strict); 2788 return Sparsity(size1(), size2(), ret_colind, ret_row); 2789 } 2790 find(std::vector<casadi_int> & loc,bool ind1) const2791 void SparsityInternal::find(std::vector<casadi_int>& loc, bool ind1) const { 2792 casadi_assert(!mul_overflows(size1(), size2()), "Integer overflow detected"); 2793 if (is_dense()) { 2794 loc = range(ind1, numel()+ind1); 2795 return; 2796 } 2797 const casadi_int* colind = this->colind(); 2798 const casadi_int* row = this->row(); 2799 2800 // Element for each nonzero 2801 loc.resize(nnz()); 2802 2803 // Loop over columns 2804 for (casadi_int cc=0; cc<size2(); ++cc) { 2805 2806 // Loop over the nonzeros 2807 for (casadi_int el=colind[cc]; el<colind[cc+1]; ++el) { 2808 2809 // Get row 2810 casadi_int rr = row[el]; 2811 2812 // Get the element 2813 loc[el] = rr+cc*size1()+ind1; 2814 } 2815 } 2816 } 2817 get_nz(std::vector<casadi_int> & indices) const2818 void SparsityInternal::get_nz(std::vector<casadi_int>& indices) const { 2819 // Quick return if no elements 2820 if (indices.empty()) return; 2821 // In a dense matrix, all indices can be found 2822 if (is_dense()) return; 2823 const casadi_int* colind = this->colind(); 2824 const casadi_int* row = this->row(); 2825 2826 // Make a sanity check 2827 casadi_int last=-1; 2828 for (vector<casadi_int>::iterator it=indices.begin(); it!=indices.end(); ++it) { 2829 if (*it>=0) { 2830 casadi_int el = *it; 2831 if (el<last) { 2832 // Sort rr in nondecreasing order, if needed 2833 std::vector<casadi_int> indices_sorted, mapping; 2834 sort(indices, indices_sorted, mapping, false); 2835 get_nz(indices_sorted); 2836 for (size_t i=0; i<indices.size(); ++i) { 2837 indices[mapping[i]] = indices_sorted[i]; 2838 } 2839 return; 2840 } 2841 last = el; 2842 } 2843 } 2844 2845 // Quick return if no elements 2846 if (last<0) return; 2847 2848 // Iterator to input/output 2849 vector<casadi_int>::iterator it=indices.begin(); 2850 while (*it<0) it++; // first non-ignored 2851 2852 // Position in flattened matrix 2853 casadi_int cur_pos = -1; 2854 2855 casadi_int col_pos = 0; 2856 2857 // Loop over columns 2858 for (casadi_int i=0; i<size2(); ++i, col_pos+=size1()) { 2859 2860 // Last position in flattened matrix for current column 2861 casadi_int last_pos = -1; 2862 2863 // Early skip to next column 2864 if (colind[i+1]>colind[i]) { 2865 casadi_int el = colind[i+1] - 1; 2866 casadi_int j = row[el]; 2867 last_pos = col_pos + j; 2868 } else { 2869 continue; 2870 } 2871 2872 // Loop over the nonzeros 2873 for (casadi_int el=colind[i]; el<colind[i+1] && last_pos >= *it; ++el) { 2874 // Get row 2875 casadi_int j = row[el]; 2876 2877 cur_pos = col_pos + j; 2878 2879 // Add leading elements not in pattern 2880 while (*it < cur_pos) { 2881 // Mark as not found 2882 *it = -1; 2883 if (++it==indices.end()) return; 2884 } 2885 2886 while (cur_pos == *it) { 2887 // Save element index 2888 *it = el; 2889 2890 // Increase index and terminate if end of vector reached 2891 do { 2892 if (++it==indices.end()) return; 2893 } while (*it<0); 2894 } 2895 } 2896 } 2897 2898 // Add trailing elements not in pattern 2899 fill(it, indices.end(), -1); 2900 } 2901 uni_coloring(const Sparsity & AT,casadi_int cutoff) const2902 Sparsity SparsityInternal::uni_coloring(const Sparsity& AT, casadi_int cutoff) const { 2903 2904 // Allocate temporary vectors 2905 vector<casadi_int> forbiddenColors; 2906 forbiddenColors.reserve(size2()); 2907 vector<casadi_int> color(size2(), 0); 2908 2909 // Access the sparsity of the transpose 2910 const casadi_int* AT_colind = AT.colind(); 2911 const casadi_int* AT_row = AT.row(); 2912 const casadi_int* colind = this->colind(); 2913 const casadi_int* row = this->row(); 2914 2915 // Loop over columns 2916 for (casadi_int i=0; i<size2(); ++i) { 2917 2918 // Loop over nonzero elements 2919 for (casadi_int el=colind[i]; el<colind[i+1]; ++el) { 2920 2921 // Get row 2922 casadi_int c = row[el]; 2923 2924 // Loop over previous columns that have an element in row c 2925 for (casadi_int el_prev=AT_colind[c]; el_prev<AT_colind[c+1]; ++el_prev) { 2926 2927 // Get the col 2928 casadi_int i_prev = AT_row[el_prev]; 2929 2930 // Escape loop if we have arrived at the current col 2931 if (i_prev>=i) 2932 break; 2933 2934 // Get the color of the col 2935 casadi_int color_prev = color[i_prev]; 2936 2937 // Mark the color as forbidden for the current col 2938 forbiddenColors[color_prev] = i; 2939 } 2940 } 2941 2942 // Get the first nonforbidden color 2943 casadi_int color_i; 2944 for (color_i=0; color_i<forbiddenColors.size(); ++color_i) { 2945 // Break if color is ok 2946 if (forbiddenColors[color_i]!=i) break; 2947 } 2948 color[i] = color_i; 2949 2950 // Add color if reached end 2951 if (color_i==forbiddenColors.size()) { 2952 forbiddenColors.push_back(0); 2953 2954 // Cutoff if too many colors 2955 if (forbiddenColors.size()>cutoff) { 2956 return Sparsity(); 2957 } 2958 } 2959 } 2960 2961 // Create return sparsity containing the coloring 2962 vector<casadi_int> ret_colind(forbiddenColors.size()+1, 0), ret_row; 2963 2964 // Get the number of rows for each col 2965 for (casadi_int i=0; i<color.size(); ++i) { 2966 ret_colind[color[i]+1]++; 2967 } 2968 2969 // Cumsum 2970 for (casadi_int j=0; j<forbiddenColors.size(); ++j) { 2971 ret_colind[j+1] += ret_colind[j]; 2972 } 2973 2974 // Get row for each col 2975 ret_row.resize(color.size()); 2976 for (casadi_int j=0; j<ret_row.size(); ++j) { 2977 ret_row[ret_colind[color[j]]++] = j; 2978 } 2979 2980 // Swap index back one step 2981 for (casadi_int j=ret_colind.size()-2; j>=0; --j) { 2982 ret_colind[j+1] = ret_colind[j]; 2983 } 2984 ret_colind[0] = 0; 2985 2986 // Return the coloring 2987 return Sparsity(size2(), forbiddenColors.size(), ret_colind, ret_row); 2988 ; 2989 } 2990 star_coloring2(casadi_int ordering,casadi_int cutoff) const2991 Sparsity SparsityInternal::star_coloring2(casadi_int ordering, casadi_int cutoff) const { 2992 if (!is_square()) { 2993 // NOTE(@jaeandersson) Why warning and not error? 2994 casadi_message("StarColoring requires a square matrix, got " + dim() + "."); 2995 } 2996 2997 // TODO(Joel): What we need here, is a distance-2 smallest last ordering 2998 // Reorder, if necessary 2999 const casadi_int* colind = this->colind(); 3000 const casadi_int* row = this->row(); 3001 if (ordering!=0) { 3002 casadi_assert_dev(ordering==1); 3003 3004 // Ordering 3005 vector<casadi_int> ord = largest_first(); 3006 3007 // Create a new sparsity pattern 3008 Sparsity sp_permuted = pmult(ord, true, true, true); 3009 3010 // Star coloring for the permuted matrix 3011 Sparsity ret_permuted = sp_permuted.star_coloring2(0); 3012 3013 // Permute result back 3014 return ret_permuted.pmult(ord, true, false, false); 3015 } 3016 3017 // Allocate temporary vectors 3018 vector<casadi_int> forbiddenColors; 3019 forbiddenColors.reserve(size2()); 3020 vector<casadi_int> color(size2(), -1); 3021 3022 vector<casadi_int> firstNeighborP(size2(), -1); 3023 vector<casadi_int> firstNeighborQ(size2(), -1); 3024 vector<casadi_int> firstNeighborQ_el(size2(), -1); 3025 3026 vector<casadi_int> treated(size2(), -1); 3027 vector<casadi_int> hub(nnz_upper(), -1); 3028 3029 vector<casadi_int> Tmapping; 3030 transpose(Tmapping); 3031 3032 vector<casadi_int> star(nnz()); 3033 casadi_int k = 0; 3034 for (casadi_int i=0; i<size2(); ++i) { 3035 for (casadi_int j_el=colind[i]; j_el<colind[i+1]; ++j_el) { 3036 casadi_int j = row[j_el]; 3037 if (i<j) { 3038 star[j_el] = k; 3039 star[Tmapping[j]] = k; 3040 k++; 3041 } 3042 } 3043 } 3044 3045 3046 3047 casadi_int starID = 0; 3048 3049 // 3: for each v \in V do 3050 for (casadi_int v=0; v<size2(); ++v) { 3051 3052 // 4: for each colored w \in N1(v) do 3053 for (casadi_int w_el=colind[v]; w_el<colind[v+1]; ++w_el) { 3054 casadi_int w = row[w_el]; 3055 casadi_int colorW = color[w]; 3056 if (colorW==-1) continue; 3057 3058 // 5: forbiddenColors[color[w]] <- v 3059 forbiddenColors[colorW] = v; 3060 3061 // 6: (p, q) <- firstNeighbor[color[w]] 3062 casadi_int p = firstNeighborP[colorW]; 3063 casadi_int q = firstNeighborQ[colorW]; 3064 3065 // 7: if p = v then < Case 1 3066 if (v==p) { 3067 3068 // 8: if treated[q] != v then 3069 if (treated[q]!=v) { 3070 3071 // 9: treat(v, q) < forbid colors of neighbors of q 3072 3073 // treat@2: for each colored x \in N1 (q) do 3074 for (casadi_int x_el=colind[q]; x_el<colind[q+1]; ++x_el) { 3075 casadi_int x = row[x_el]; 3076 if (color[x]==-1) continue; 3077 3078 // treat@3: forbiddenColors[color[x]] <- v 3079 forbiddenColors[color[x]] = v; 3080 } 3081 3082 // treat@4: treated[q] <- v 3083 treated[q] = v; 3084 3085 } 3086 // 10: treat(v, w) < forbid colors of neighbors of w 3087 3088 // treat@2: for each colored x \in N1 (w) do 3089 for (casadi_int x_el=colind[w]; x_el<colind[w+1]; ++x_el) { 3090 casadi_int x = row[x_el]; 3091 if (color[x]==-1) continue; 3092 3093 // treat@3: forbiddenColors[color[x]] <- v 3094 forbiddenColors[color[x]] = v; 3095 } 3096 3097 // treat@4: treated[w] <- v 3098 treated[w] = v; 3099 3100 // 11: else 3101 } else { 3102 3103 // 12: firstNeighbor[color[w]] <- (v, w) 3104 firstNeighborP[colorW] = v; 3105 firstNeighborQ[colorW] = w; 3106 firstNeighborQ_el[colorW] = w_el; 3107 3108 // 13: for each colored vertex x \in N1 (w) do 3109 casadi_int x_el_end = colind[w+1]; 3110 casadi_int x, colorx; 3111 for (casadi_int x_el=colind[w]; x_el < x_el_end; ++x_el) { 3112 x = row[x_el]; 3113 colorx = color[x]; 3114 if (colorx==-1 || x==v) continue; 3115 3116 // 14: if x = hub[star[wx]] then potential Case 2 3117 if (hub[star[x_el]]==x) { 3118 3119 // 15: forbiddenColors[color[x]] <- v 3120 forbiddenColors[colorx] = v; 3121 3122 } 3123 } 3124 } 3125 3126 } 3127 3128 // 16: color[v] <- min {c > 0 : forbiddenColors[c] != v} 3129 bool new_color = true; 3130 for (casadi_int color_i=0; color_i<forbiddenColors.size(); ++color_i) { 3131 // Break if color is ok 3132 if (forbiddenColors[color_i]!=v) { 3133 color[v] = color_i; 3134 new_color = false; 3135 break; 3136 } 3137 } 3138 3139 // New color if reached end 3140 if (new_color) { 3141 color[v] = forbiddenColors.size(); 3142 forbiddenColors.push_back(-1); 3143 3144 // Cutoff if too many colors 3145 if (forbiddenColors.size()>cutoff) { 3146 return Sparsity(); 3147 } 3148 } 3149 3150 // 17: updateStars(v) 3151 3152 // updateStars@2: for each colored w \in N1 (v) do 3153 for (casadi_int w_el=colind[v]; w_el<colind[v+1]; ++w_el) { 3154 casadi_int w = row[w_el]; 3155 casadi_int colorW = color[w]; 3156 if (colorW==-1) continue; 3157 3158 // updateStars@3: if exits x \in N1 (w) where x = v and color[x] = color[v] then 3159 bool check = false; 3160 casadi_int x; 3161 casadi_int x_el; 3162 for (x_el=colind[w]; x_el<colind[w+1]; ++x_el) { 3163 x = row[x_el]; 3164 if (x==v || color[x]!=color[v]) continue; 3165 check = true; 3166 break; 3167 } 3168 if (check) { 3169 3170 // updateStars@4: hub[star[wx]] <- w 3171 casadi_int starwx = star[x_el]; 3172 hub[starwx] = w; 3173 3174 // updateStars@5: star[vw] <- star[wx] 3175 star[w_el] = starwx; 3176 star[Tmapping[w_el]] = starwx; 3177 3178 // updateStars@6: else 3179 } else { 3180 3181 // updateStars@7: (p, q) <- firstNeighbor[color[w]] 3182 casadi_int p = firstNeighborP[colorW]; 3183 casadi_int q = firstNeighborQ[colorW]; 3184 casadi_int q_el = firstNeighborQ_el[colorW]; 3185 3186 // updateStars@8: if (p = v) and (q = w) then 3187 if (p==v && q!=w) { 3188 3189 // updateStars@9: hub[star[vq]] <- v 3190 casadi_int starvq = star[q_el]; 3191 hub[starvq] = v; 3192 3193 // updateStars@10: star[vw] <- star[vq] 3194 star[w_el] = starvq; 3195 star[Tmapping[w_el]] = starvq; 3196 3197 // updateStars@11: else 3198 } else { 3199 3200 // updateStars@12: starID <- starID + 1 3201 starID+= 1; 3202 3203 // updateStars@13: star[vw] <- starID 3204 star[w_el] = starID; 3205 star[Tmapping[w_el]]= starID; 3206 3207 } 3208 3209 } 3210 3211 } 3212 3213 } 3214 3215 // Create return sparsity containing the coloring 3216 vector<casadi_int> ret_colind(forbiddenColors.size()+1, 0), ret_row; 3217 3218 // Get the number of rows for each col 3219 for (casadi_int i=0; i<color.size(); ++i) { 3220 ret_colind[color[i]+1]++; 3221 } 3222 3223 // Cumsum 3224 for (casadi_int j=0; j<forbiddenColors.size(); ++j) { 3225 ret_colind[j+1] += ret_colind[j]; 3226 } 3227 3228 // Get row for each col 3229 ret_row.resize(color.size()); 3230 for (casadi_int j=0; j<ret_row.size(); ++j) { 3231 ret_row[ret_colind[color[j]]++] = j; 3232 } 3233 3234 // Swap index back one step 3235 for (casadi_int j=ret_colind.size()-2; j>=0; --j) { 3236 ret_colind[j+1] = ret_colind[j]; 3237 } 3238 ret_colind[0] = 0; 3239 3240 // Return the coloring 3241 return Sparsity(size2(), forbiddenColors.size(), ret_colind, ret_row); 3242 } 3243 star_coloring(casadi_int ordering,casadi_int cutoff) const3244 Sparsity SparsityInternal::star_coloring(casadi_int ordering, casadi_int cutoff) const { 3245 if (!is_square()) { 3246 // NOTE(@jaeandersson) Why warning and not error? 3247 casadi_message("StarColoring requires a square matrix, got " + dim() + "."); 3248 } 3249 3250 // Reorder, if necessary 3251 if (ordering!=0) { 3252 casadi_assert_dev(ordering==1); 3253 3254 // Ordering 3255 vector<casadi_int> ord = largest_first(); 3256 3257 // Create a new sparsity pattern 3258 Sparsity sp_permuted = pmult(ord, true, true, true); 3259 3260 // Star coloring for the permuted matrix 3261 Sparsity ret_permuted = sp_permuted.star_coloring(0); 3262 3263 // Permute result back 3264 return ret_permuted.pmult(ord, true, false, false); 3265 } 3266 3267 // Allocate temporary vectors 3268 const casadi_int* colind = this->colind(); 3269 const casadi_int* row = this->row(); 3270 vector<casadi_int> forbiddenColors; 3271 forbiddenColors.reserve(size2()); 3272 vector<casadi_int> color(size2(), -1); 3273 3274 // 4: for i <- 1 to |V | do 3275 for (casadi_int i=0; i<size2(); ++i) { 3276 3277 // 5: for each w \in N1 (vi) do 3278 for (casadi_int w_el=colind[i]; w_el<colind[i+1]; ++w_el) { 3279 casadi_int w = row[w_el]; 3280 3281 // 6: if w is colored then 3282 if (color[w]!=-1) { 3283 3284 // 7: forbiddenColors[color[w]] <- v 3285 forbiddenColors[color[w]] = i; 3286 3287 } // 8: end if 3288 3289 // 9: for each colored vertex x \in N1 (w) do 3290 for (casadi_int x_el=colind[w]; x_el<colind[w+1]; ++x_el) { 3291 casadi_int x = row[x_el]; 3292 if (color[x]==-1) continue; 3293 3294 // 10: if w is not colored then 3295 if (color[w]==-1) { 3296 3297 //11: forbiddenColors[color[x]] <- vi 3298 forbiddenColors[color[x]] = i; 3299 3300 } else { // 12: else 3301 3302 // 13: for each colored vertex y \in N1 (x), y != w do 3303 for (casadi_int y_el=colind[x]; y_el<colind[x+1]; ++y_el) { 3304 casadi_int y = row[y_el]; 3305 if (color[y]==-1 || y==w) continue; 3306 3307 // 14: if color[y] = color[w] then 3308 if (color[y]==color[w]) { 3309 3310 // 15: forbiddenColors[color[x]] <- vi 3311 forbiddenColors[color[x]] = i; 3312 3313 // 16: break 3314 break; 3315 3316 } // 17: end if 3317 3318 } // 18: end for 3319 3320 } // 19: end if 3321 3322 } // 20 end for 3323 3324 } // 21 end for 3325 3326 // 22: color[v] <- min {c > 0 : forbiddenColors[c] = v} 3327 bool new_color = true; 3328 for (casadi_int color_i=0; color_i<forbiddenColors.size(); ++color_i) { 3329 // Break if color is ok 3330 if (forbiddenColors[color_i]!=i) { 3331 color[i] = color_i; 3332 new_color = false; 3333 break; 3334 } 3335 } 3336 3337 // New color if reached end 3338 if (new_color) { 3339 color[i] = forbiddenColors.size(); 3340 forbiddenColors.push_back(-1); 3341 3342 // Cutoff if too many colors 3343 if (forbiddenColors.size()>cutoff) { 3344 return Sparsity(); 3345 } 3346 } 3347 3348 } // 23 end for 3349 3350 // Number of colors used 3351 casadi_int num_colors = forbiddenColors.size(); 3352 3353 // Return sparsity in sparse triplet format 3354 return Sparsity::triplet(size2(), num_colors, range(color.size()), color); 3355 } 3356 largest_first() const3357 std::vector<casadi_int> SparsityInternal::largest_first() const { 3358 vector<casadi_int> degree = get_colind(); 3359 casadi_int max_degree = 0; 3360 for (casadi_int k=0; k<size2(); ++k) { 3361 degree[k] = degree[k+1]-degree[k]; 3362 max_degree = max(max_degree, 1+degree[k]); 3363 } 3364 degree.resize(size2()); 3365 3366 // Vector for binary sort 3367 vector<casadi_int> degree_count(max_degree+1, 0); 3368 for (vector<casadi_int>::const_iterator it=degree.begin(); it!=degree.end(); ++it) { 3369 degree_count.at(*it+1)++; 3370 } 3371 3372 // Cumsum to get the offset for each degree 3373 for (casadi_int d=0; d<max_degree; ++d) { 3374 degree_count[d+1] += degree_count[d]; 3375 } 3376 3377 // Now a bucket sort 3378 vector<casadi_int> ordering(size2()); 3379 for (casadi_int k=size2()-1; k>=0; --k) { 3380 ordering[degree_count[degree[k]]++] = k; 3381 } 3382 3383 // Invert the ordering 3384 vector<casadi_int>& reverse_ordering = degree_count; // reuse memory 3385 reverse_ordering.resize(ordering.size()); 3386 copy(ordering.begin(), ordering.end(), reverse_ordering.rbegin()); 3387 3388 // Return the ordering 3389 return reverse_ordering; 3390 } 3391 pmult(const std::vector<casadi_int> & p,bool permute_rows,bool permute_columns,bool invert_permutation) const3392 Sparsity SparsityInternal::pmult(const std::vector<casadi_int>& p, bool permute_rows, 3393 bool permute_columns, bool invert_permutation) const { 3394 // Invert p, possibly 3395 vector<casadi_int> p_inv; 3396 if (invert_permutation) { 3397 p_inv.resize(p.size()); 3398 for (casadi_int k=0; k<p.size(); ++k) { 3399 p_inv[p[k]] = k; 3400 } 3401 } 3402 const vector<casadi_int>& pp = invert_permutation ? p_inv : p; 3403 3404 // Get columns 3405 vector<casadi_int> col = get_col(); 3406 3407 // Get rows 3408 const casadi_int* row = this->row(); 3409 3410 // Sparsity of the return matrix 3411 vector<casadi_int> new_row(col.size()), new_col(col.size()); 3412 3413 // Possibly permute columns 3414 if (permute_columns) { 3415 // Assert dimensions 3416 casadi_assert_dev(p.size()==size2()); 3417 3418 // Permute 3419 for (casadi_int k=0; k<col.size(); ++k) { 3420 new_col[k] = pp[col[k]]; 3421 } 3422 3423 } else { 3424 // No permutation of columns 3425 copy(col.begin(), col.end(), new_col.begin()); 3426 } 3427 3428 // Possibly permute rows 3429 if (permute_rows) { 3430 // Assert dimensions 3431 casadi_assert_dev(p.size()==size1()); 3432 3433 // Permute 3434 for (casadi_int k=0; k<nnz(); ++k) { 3435 new_row[k] = pp[row[k]]; 3436 } 3437 3438 } else { 3439 // No permutation of rows 3440 copy(row, row+nnz(), new_row.begin()); 3441 } 3442 3443 // Return permuted matrix 3444 return Sparsity::triplet(size1(), size2(), new_row, new_col); 3445 } 3446 is_transpose(const SparsityInternal & y) const3447 bool SparsityInternal::is_transpose(const SparsityInternal& y) const { 3448 // Assert dimensions and number of nonzeros 3449 if (size2()!=y.size1() || size1()!=y.size2() || nnz()!=y.nnz()) 3450 return false; 3451 3452 // Quick return if empty interior or dense 3453 if (nnz()==0 || is_dense()) 3454 return true; 3455 3456 // Run algorithm on the pattern with the least number of rows 3457 if (size1()>size2()) return y.is_transpose(*this); 3458 3459 // Index counter for columns of the possible transpose 3460 vector<casadi_int> y_col_count(y.size2(), 0); 3461 const casadi_int* colind = this->colind(); 3462 const casadi_int* row = this->row(); 3463 const casadi_int* y_colind = y.colind(); 3464 const casadi_int* y_row = y.row(); 3465 3466 // Loop over the columns 3467 for (casadi_int i=0; i<size2(); ++i) { 3468 3469 // Loop over the nonzeros 3470 for (casadi_int el=colind[i]; el<colind[i+1]; ++el) { 3471 3472 // Get the row 3473 casadi_int j=row[el]; 3474 3475 // Get the element of the possible transpose 3476 casadi_int el_y = y_colind[j] + y_col_count[j]++; 3477 3478 // Quick return if element doesn't exist 3479 if (el_y>=y_colind[j+1]) return false; 3480 3481 // Get the row of the possible transpose 3482 casadi_int j_y = y_row[el_y]; 3483 3484 // Quick return if mismatch 3485 if (j_y != i) return false; 3486 } 3487 } 3488 3489 // Transpose if reached this point 3490 return true; 3491 } 3492 is_reshape(const SparsityInternal & y) const3493 bool SparsityInternal::is_reshape(const SparsityInternal& y) const { 3494 // Quick return if the objects are the same 3495 if (this==&y) return true; 3496 3497 // Check if same number of entries and nonzeros 3498 if (numel()!=y.numel() || nnz()!=y.nnz()) return false; 3499 3500 // Quick return if empty interior or dense 3501 if (nnz()==0 || is_dense()) return true; 3502 3503 // Get Pattern 3504 const casadi_int* colind = this->colind(); 3505 const casadi_int* row = this->row(); 3506 const casadi_int* y_colind = y.colind(); 3507 const casadi_int* y_row = y.row(); 3508 3509 // If same number of rows, check if patterns are identical 3510 if (size1()==y.size1()) return is_equal(y.size1(), y.size2(), y_colind, y_row); 3511 3512 // Loop over the elements 3513 for (casadi_int cc=0; cc<size2(); ++cc) { 3514 for (casadi_int el=colind[cc]; el<colind[cc+1]; ++el) { 3515 casadi_int rr=row[el]; 3516 3517 // Get row and column of y 3518 casadi_int loc = rr+size1()*cc; 3519 casadi_int rr_y = loc % y.size1(); 3520 casadi_int cc_y = loc / y.size1(); 3521 3522 // Make sure matching 3523 if (rr_y != y_row[el] || el<y_colind[cc_y] || el>=y_colind[cc_y+1]) 3524 return false; 3525 } 3526 } 3527 3528 // Reshape if reached this point 3529 return true; 3530 } 3531 spy(std::ostream & stream) const3532 void SparsityInternal::spy(std::ostream &stream) const { 3533 3534 // Index counter for each column 3535 std::vector<casadi_int> cind = get_colind(); 3536 const casadi_int* colind = this->colind(); 3537 const casadi_int* row = this->row(); 3538 3539 // Loop over rows 3540 for (casadi_int rr=0; rr<size1(); ++rr) { 3541 3542 // Loop over columns 3543 for (casadi_int cc=0; cc<size2(); ++cc) { 3544 // Check if nonzero 3545 if (cind[cc]<colind[cc+1] && row[cind[cc]]==rr) { 3546 stream << "*"; 3547 cind[cc]++; 3548 } else { 3549 stream << "."; 3550 } 3551 } 3552 3553 // End of row 3554 stream << endl; 3555 } 3556 } 3557 export_code(const std::string & lang,std::ostream & stream,const Dict & options) const3558 void SparsityInternal::export_code(const std::string& lang, 3559 std::ostream &stream, const Dict& options) const { 3560 casadi_assert(lang=="matlab", "Only matlab language supported for now."); 3561 3562 // Default values for options 3563 bool opt_inline = false; 3564 std::string name = "sp"; 3565 bool as_matrix = true; 3566 casadi_int indent_level = 0; 3567 3568 // Read options 3569 for (auto&& op : options) { 3570 if (op.first=="inline") { 3571 opt_inline = op.second; 3572 } else if (op.first=="name") { 3573 name = op.second.to_string(); 3574 } else if (op.first=="as_matrix") { 3575 as_matrix = op.second; 3576 } else if (op.first=="indent_level") { 3577 indent_level = op.second; 3578 } else { 3579 casadi_error("Unknown option '" + op.first + "'."); 3580 } 3581 } 3582 3583 // Construct indent string 3584 std::string indent; 3585 for (casadi_int i=0;i<indent_level;++i) { 3586 indent += " "; 3587 } 3588 3589 casadi_assert(!opt_inline, "Inline not supported for now."); 3590 3591 // Export dimensions 3592 stream << indent << name << "_m = " << size1() << ";" << endl; 3593 stream << indent << name << "_n = " << size2() << ";" << endl; 3594 3595 // Matlab indices are one-based 3596 const casadi_int index_offset = 1; 3597 3598 // Print columns 3599 const casadi_int* colind = this->colind(); 3600 const casadi_int* row = this->row(); 3601 stream << indent << name<< "_j = ["; 3602 bool first = true; 3603 for (casadi_int i=0; i<size2(); ++i) { 3604 for (casadi_int el=colind[i]; el<colind[i+1]; ++el) { 3605 if (!first) stream << ", "; 3606 stream << (i+index_offset); 3607 first = false; 3608 } 3609 } 3610 stream << "];" << endl; 3611 3612 // Print rows 3613 stream << indent << name << "_i = ["; 3614 first = true; 3615 casadi_int nz = nnz(); 3616 for (casadi_int i=0; i<nz; ++i) { 3617 if (!first) stream << ", "; 3618 stream << (row[i]+index_offset); 3619 first = false; 3620 } 3621 stream << "];" << endl; 3622 3623 if (as_matrix) { 3624 // Generate matrix 3625 stream << indent << name << " = sparse(" << name << "_i, " << name << "_j, "; 3626 stream << "ones(size(" << name << "_i)), "; 3627 stream << name << "_m, " << name << "_n);" << endl; 3628 } 3629 3630 } 3631 spy_matlab(const std::string & mfile_name) const3632 void SparsityInternal::spy_matlab(const std::string& mfile_name) const { 3633 // Create the .m file 3634 ofstream mfile; 3635 mfile.open(mfile_name.c_str()); 3636 3637 // Header 3638 mfile << "% This function was automatically generated by CasADi" << endl; 3639 3640 Dict opts; 3641 opts["name"] = "A"; 3642 export_code("matlab", mfile, opts); 3643 3644 // Issue spy command 3645 mfile << "spy(A);" << endl; 3646 3647 mfile.close(); 3648 } 3649 hash() const3650 std::size_t SparsityInternal::hash() const { 3651 return hash_sparsity(size1(), size2(), colind(), row()); 3652 } 3653 is_tril() const3654 bool SparsityInternal::is_tril() const { 3655 const casadi_int* colind = this->colind(); 3656 const casadi_int* row = this->row(); 3657 // loop over columns 3658 for (casadi_int i=0; i<size2(); ++i) { 3659 if (colind[i] != colind[i+1]) { // if there are any elements of the column 3660 // check row of the top-most element of the column 3661 casadi_int rr = row[colind[i]]; 3662 3663 // not lower triangular if row>i 3664 if (rr<i) return false; 3665 } 3666 } 3667 // all columns ok 3668 return true; 3669 } 3670 is_triu() const3671 bool SparsityInternal::is_triu() const { 3672 const casadi_int* colind = this->colind(); 3673 const casadi_int* row = this->row(); 3674 // loop over columns 3675 for (casadi_int i=0; i<size2(); ++i) { 3676 if (colind[i] != colind[i+1]) { // if there are any elements of the column 3677 // check row of the bottom-most element of the column 3678 casadi_int rr = row[colind[i+1]-1]; 3679 3680 // not upper triangular if row>i 3681 if (rr>i) return false; 3682 } 3683 } 3684 // all columns ok 3685 return true; 3686 } 3687 _tril(bool includeDiagonal) const3688 Sparsity SparsityInternal::_tril(bool includeDiagonal) const { 3689 const casadi_int* colind = this->colind(); 3690 const casadi_int* row = this->row(); 3691 vector<casadi_int> ret_colind, ret_row; 3692 ret_colind.reserve(size2()+1); 3693 ret_colind.push_back(0); 3694 for (casadi_int cc=0; cc<size2(); ++cc) { 3695 for (casadi_int el=colind[cc]; el<colind[cc+1]; ++el) { 3696 casadi_int rr=row[el]; 3697 if (rr>cc || (includeDiagonal && rr==cc)) { 3698 ret_row.push_back(rr); 3699 } 3700 } 3701 ret_colind.push_back(ret_row.size()); 3702 } 3703 return Sparsity(size1(), size2(), ret_colind, ret_row); 3704 } 3705 _triu(bool includeDiagonal) const3706 Sparsity SparsityInternal::_triu(bool includeDiagonal) const { 3707 const casadi_int* colind = this->colind(); 3708 const casadi_int* row = this->row(); 3709 vector<casadi_int> ret_colind, ret_row; 3710 ret_colind.reserve(size2()+1); 3711 ret_colind.push_back(0); 3712 for (casadi_int cc=0; cc<size2(); ++cc) { 3713 for (casadi_int el=colind[cc]; el<colind[cc+1]; ++el) { 3714 casadi_int rr=row[el]; 3715 if (rr<cc || (includeDiagonal && rr==cc)) { 3716 ret_row.push_back(rr); 3717 } 3718 } 3719 ret_colind.push_back(ret_row.size()); 3720 } 3721 return Sparsity(size1(), size2(), ret_colind, ret_row); 3722 } 3723 get_lower() const3724 std::vector<casadi_int> SparsityInternal::get_lower() const { 3725 const casadi_int* colind = this->colind(); 3726 const casadi_int* row = this->row(); 3727 vector<casadi_int> ret; 3728 for (casadi_int cc=0; cc<size2(); ++cc) { 3729 for (casadi_int el = colind[cc]; el<colind[cc+1]; ++el) { 3730 if (row[el]>=cc) { 3731 ret.push_back(el); 3732 } 3733 } 3734 } 3735 return ret; 3736 } 3737 get_upper() const3738 std::vector<casadi_int> SparsityInternal::get_upper() const { 3739 const casadi_int* colind = this->colind(); 3740 const casadi_int* row = this->row(); 3741 vector<casadi_int> ret; 3742 for (casadi_int cc=0; cc<size2(); ++cc) { 3743 for (casadi_int el = colind[cc]; el<colind[cc+1] && row[el]<=cc; ++el) { 3744 ret.push_back(el); 3745 } 3746 } 3747 return ret; 3748 } 3749 bw_upper() const3750 casadi_int SparsityInternal::bw_upper() const { 3751 casadi_int bw = 0; 3752 const casadi_int* colind = this->colind(); 3753 const casadi_int* row = this->row(); 3754 for (casadi_int cc=0; cc<size2(); ++cc) { 3755 if (colind[cc] != colind[cc+1]) { // if there are any elements of the column 3756 casadi_int rr = row[colind[cc]]; 3757 bw = std::max(bw, cc-rr); 3758 } 3759 } 3760 return bw; 3761 } 3762 bw_lower() const3763 casadi_int SparsityInternal::bw_lower() const { 3764 casadi_int bw = 0; 3765 const casadi_int* colind = this->colind(); 3766 const casadi_int* row = this->row(); 3767 for (casadi_int cc=0; cc<size2(); ++cc) { 3768 if (colind[cc] != colind[cc+1]) { // if there are any elements of the column 3769 casadi_int rr = row[colind[cc+1]-1]; 3770 bw = std::max(bw, rr-cc); 3771 } 3772 } 3773 return bw; 3774 } 3775 get_colind() const3776 vector<casadi_int> SparsityInternal::get_colind() const { 3777 const casadi_int* colind = this->colind(); 3778 return vector<casadi_int>(colind, colind+size2()+1); 3779 } 3780 get_row() const3781 vector<casadi_int> SparsityInternal::get_row() const { 3782 const casadi_int* row = this->row(); 3783 return vector<casadi_int>(row, row+nnz()); 3784 } 3785 3786 void SparsityInternal:: spsolve(bvec_t * X,const bvec_t * B,bool tr) const3787 spsolve(bvec_t* X, const bvec_t* B, bool tr) const { 3788 const Btf& btf = this->btf(); 3789 const casadi_int* colind = this->colind(); 3790 const casadi_int* row = this->row(); 3791 3792 if (!tr) { 3793 for (casadi_int b=0; b<btf.nb; ++b) { // loop over the blocks forward 3794 3795 // Get dependencies from all right-hand-sides in the block ... 3796 bvec_t block_dep = 0; 3797 for (casadi_int el=btf.rowblock[b]; el<btf.rowblock[b+1]; ++el) { 3798 casadi_int rr = btf.rowperm[el]; 3799 block_dep |= B[rr]; 3800 } 3801 3802 // ... as well as all other variables in the block 3803 for (casadi_int el=btf.colblock[b]; el<btf.colblock[b+1]; ++el) { 3804 casadi_int cc = btf.colperm[el]; 3805 block_dep |= X[cc]; 3806 } 3807 3808 // Propagate ... 3809 for (casadi_int el=btf.colblock[b]; el<btf.colblock[b+1]; ++el) { 3810 casadi_int cc = btf.colperm[el]; 3811 3812 // ... to all variables in the block ... 3813 X[cc] |= block_dep; 3814 3815 // ... as well as to other variables which depends on variables in the block 3816 for (casadi_int k=colind[cc]; k<colind[cc+1]; ++k) { 3817 casadi_int rr=row[k]; 3818 X[rr] |= block_dep; 3819 } 3820 } 3821 } 3822 3823 } else { // transpose 3824 for (casadi_int b=btf.nb-1; b>=0; --b) { // loop over the blocks backward 3825 3826 // Get dependencies ... 3827 bvec_t block_dep = 0; 3828 for (casadi_int el=btf.colblock[b]; el<btf.colblock[b+1]; ++el) { 3829 casadi_int cc = btf.colperm[el]; 3830 3831 // .. from all right-hand-sides in the block ... 3832 block_dep |= B[cc]; 3833 3834 // ... as well as from all depending variables ... 3835 for (casadi_int k=colind[cc]; k<colind[cc+1]; ++k) { 3836 casadi_int rr=row[k]; 3837 block_dep |= X[rr]; 3838 } 3839 } 3840 3841 // Propagate to all variables in the block 3842 for (casadi_int el=btf.rowblock[b]; el<btf.rowblock[b+1]; ++el) { 3843 casadi_int rr = btf.rowperm[el]; 3844 X[rr] |= block_dep; 3845 } 3846 } 3847 } 3848 } 3849 3850 } // namespace casadi 3851