/usr/include/suitesparse/btf.h is in libsuitesparse-dev 1:4.2.1-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 | /* ========================================================================== */
/* === BTF package ========================================================== */
/* ========================================================================== */
/* BTF_MAXTRANS: find a column permutation Q to give A*Q a zero-free diagonal
* BTF_STRONGCOMP: find a symmetric permutation P to put P*A*P' into block
* upper triangular form.
* BTF_ORDER: do both of the above (btf_maxtrans then btf_strongcomp).
*
* By Tim Davis. Copyright (c) 2004-2007, University of Florida.
* with support from Sandia National Laboratories. All Rights Reserved.
*/
/* ========================================================================== */
/* === BTF_MAXTRANS ========================================================= */
/* ========================================================================== */
/* BTF_MAXTRANS: finds a permutation of the columns of a matrix so that it has a
* zero-free diagonal. The input is an m-by-n sparse matrix in compressed
* column form. The array Ap of size n+1 gives the starting and ending
* positions of the columns in the array Ai. Ap[0] must be zero. The array Ai
* contains the row indices of the nonzeros of the matrix A, and is of size
* Ap[n]. The row indices of column j are located in Ai[Ap[j] ... Ap[j+1]-1].
* Row indices must be in the range 0 to m-1. Duplicate entries may be present
* in any given column. The input matrix is not checked for validity (row
* indices out of the range 0 to m-1 will lead to an undeterminate result -
* possibly a core dump, for example). Row indices in any given column need
* not be in sorted order. However, if they are sorted and the matrix already
* has a zero-free diagonal, then the identity permutation is returned.
*
* The output of btf_maxtrans is an array Match of size n. If row i is matched
* with column j, then A(i,j) is nonzero, and then Match[i] = j. If the matrix
* is structurally nonsingular, all entries in the Match array are unique, and
* Match can be viewed as a column permutation if A is square. That is, column
* k of the original matrix becomes column Match[k] of the permuted matrix. In
* MATLAB, this can be expressed as (for non-structurally singular matrices):
*
* Match = maxtrans (A) ;
* B = A (:, Match) ;
*
* except of course here the A matrix and Match vector are all 0-based (rows
* and columns in the range 0 to n-1), not 1-based (rows/cols in range 1 to n).
* The MATLAB dmperm routine returns a row permutation. See the maxtrans
* mexFunction for more details.
*
* If row i is not matched to any column, then Match[i] is == -1. The
* btf_maxtrans routine returns the number of nonzeros on diagonal of the
* permuted matrix.
*
* In the MATLAB mexFunction interface to btf_maxtrans, 1 is added to the Match
* array to obtain a 1-based permutation. Thus, in MATLAB where A is m-by-n:
*
* q = maxtrans (A) ; % has entries in the range 0:n
* q % a column permutation (only if sprank(A)==n)
* B = A (:, q) ; % permuted matrix (only if sprank(A)==n)
* sum (q > 0) ; % same as "sprank (A)"
*
* This behaviour differs from p = dmperm (A) in MATLAB, which returns the
* matching as p(j)=i if row i and column j are matched, and p(j)=0 if column j
* is unmatched.
*
* p = dmperm (A) ; % has entries in the range 0:m
* p % a row permutation (only if sprank(A)==m)
* B = A (p, :) ; % permuted matrix (only if sprank(A)==m)
* sum (p > 0) ; % definition of sprank (A)
*
* This algorithm is based on the paper "On Algorithms for obtaining a maximum
* transversal" by Iain Duff, ACM Trans. Mathematical Software, vol 7, no. 1,
* pp. 315-330, and "Algorithm 575: Permutations for a zero-free diagonal",
* same issue, pp. 387-390. Algorithm 575 is MC21A in the Harwell Subroutine
* Library. This code is not merely a translation of the Fortran code into C.
* It is a completely new implementation of the basic underlying method (depth
* first search over a subgraph with nodes corresponding to columns matched so
* far, and cheap matching). This code was written with minimal observation of
* the MC21A/B code itself. See comments below for a comparison between the
* maxtrans and MC21A/B codes.
*
* This routine operates on a column-form matrix and produces a column
* permutation. MC21A uses a row-form matrix and produces a row permutation.
* The difference is merely one of convention in the comments and interpretation
* of the inputs and outputs. If you want a row permutation, simply pass a
* compressed-row sparse matrix to this routine and you will get a row
* permutation (just like MC21A). Similarly, you can pass a column-oriented
* matrix to MC21A and it will happily return a column permutation.
*/
#ifndef _BTF_H
#define _BTF_H
/* make it easy for C++ programs to include BTF */
#ifdef __cplusplus
extern "C" {
#endif
#include "SuiteSparse_config.h"
int btf_maxtrans /* returns # of columns matched */
(
/* --- input, not modified: --- */
int nrow, /* A is nrow-by-ncol in compressed column form */
int ncol,
int Ap [ ], /* size ncol+1 */
int Ai [ ], /* size nz = Ap [ncol] */
double maxwork, /* maximum amount of work to do is maxwork*nnz(A); no limit
* if <= 0 */
/* --- output, not defined on input --- */
double *work, /* work = -1 if maxwork > 0 and the total work performed
* reached the maximum of maxwork*nnz(A).
* Otherwise, work = the total work performed. */
int Match [ ], /* size nrow. Match [i] = j if column j matched to row i
* (see above for the singular-matrix case) */
/* --- workspace, not defined on input or output --- */
int Work [ ] /* size 5*ncol */
) ;
/* long integer version (all "int" parameters become "SuiteSparse_long") */
SuiteSparse_long btf_l_maxtrans (SuiteSparse_long, SuiteSparse_long,
SuiteSparse_long *, SuiteSparse_long *, double, double *,
SuiteSparse_long *, SuiteSparse_long *) ;
/* ========================================================================== */
/* === BTF_STRONGCOMP ======================================================= */
/* ========================================================================== */
/* BTF_STRONGCOMP finds the strongly connected components of a graph, returning
* a symmetric permutation. The matrix A must be square, and is provided on
* input in compressed-column form (see BTF_MAXTRANS, above). The diagonal of
* the input matrix A (or A*Q if Q is provided on input) is ignored.
*
* If Q is not NULL on input, then the strongly connected components of A*Q are
* found. Q may be flagged on input, where Q[k] < 0 denotes a flagged column k.
* The permutation is j = BTF_UNFLIP (Q [k]). On output, Q is modified (the
* flags are preserved) so that P*A*Q is in block upper triangular form.
*
* If Q is NULL, then the permutation P is returned so that P*A*P' is in upper
* block triangular form.
*
* The vector R gives the block boundaries, where block b is in rows/columns
* R[b] to R[b+1]-1 of the permuted matrix, and where b ranges from 1 to the
* number of strongly connected components found.
*/
int btf_strongcomp /* return # of strongly connected components */
(
/* input, not modified: */
int n, /* A is n-by-n in compressed column form */
int Ap [ ], /* size n+1 */
int Ai [ ], /* size nz = Ap [n] */
/* optional input, modified (if present) on output: */
int Q [ ], /* size n, input column permutation */
/* output, not defined on input */
int P [ ], /* size n. P [k] = j if row and column j are kth row/col
* in permuted matrix. */
int R [ ], /* size n+1. block b is in rows/cols R[b] ... R[b+1]-1 */
/* workspace, not defined on input or output */
int Work [ ] /* size 4n */
) ;
SuiteSparse_long btf_l_strongcomp (SuiteSparse_long, SuiteSparse_long *,
SuiteSparse_long *, SuiteSparse_long *, SuiteSparse_long *,
SuiteSparse_long *, SuiteSparse_long *) ;
/* ========================================================================== */
/* === BTF_ORDER ============================================================ */
/* ========================================================================== */
/* BTF_ORDER permutes a square matrix into upper block triangular form. It
* does this by first finding a maximum matching (or perhaps a limited matching
* if the work is limited), via the btf_maxtrans function. If a complete
* matching is not found, BTF_ORDER completes the permutation, but flags the
* columns of P*A*Q to denote which columns are not matched. If the matrix is
* structurally rank deficient, some of the entries on the diagonal of the
* permuted matrix will be zero. BTF_ORDER then calls btf_strongcomp to find
* the strongly-connected components.
*
* On output, P and Q are the row and column permutations, where i = P[k] if
* row i of A is the kth row of P*A*Q, and j = BTF_UNFLIP(Q[k]) if column j of
* A is the kth column of P*A*Q. If Q[k] < 0, then the (k,k)th entry in P*A*Q
* is structurally zero.
*
* The vector R gives the block boundaries, where block b is in rows/columns
* R[b] to R[b+1]-1 of the permuted matrix, and where b ranges from 1 to the
* number of strongly connected components found.
*/
int btf_order /* returns number of blocks found */
(
/* --- input, not modified: --- */
int n, /* A is n-by-n in compressed column form */
int Ap [ ], /* size n+1 */
int Ai [ ], /* size nz = Ap [n] */
double maxwork, /* do at most maxwork*nnz(A) work in the maximum
* transversal; no limit if <= 0 */
/* --- output, not defined on input --- */
double *work, /* return value from btf_maxtrans */
int P [ ], /* size n, row permutation */
int Q [ ], /* size n, column permutation */
int R [ ], /* size n+1. block b is in rows/cols R[b] ... R[b+1]-1 */
int *nmatch, /* # nonzeros on diagonal of P*A*Q */
/* --- workspace, not defined on input or output --- */
int Work [ ] /* size 5n */
) ;
SuiteSparse_long btf_l_order (SuiteSparse_long, SuiteSparse_long *,
SuiteSparse_long *, double , double *, SuiteSparse_long *,
SuiteSparse_long *, SuiteSparse_long *, SuiteSparse_long *,
SuiteSparse_long *) ;
/* ========================================================================== */
/* === BTF marking of singular columns ====================================== */
/* ========================================================================== */
/* BTF_FLIP is a "negation about -1", and is used to mark an integer j
* that is normally non-negative. BTF_FLIP (-1) is -1. BTF_FLIP of
* a number > -1 is negative, and BTF_FLIP of a number < -1 is positive.
* BTF_FLIP (BTF_FLIP (j)) = j for all integers j. UNFLIP (j) acts
* like an "absolute value" operation, and is always >= -1. You can test
* whether or not an integer j is "flipped" with the BTF_ISFLIPPED (j)
* macro.
*/
#define BTF_FLIP(j) (-(j)-2)
#define BTF_ISFLIPPED(j) ((j) < -1)
#define BTF_UNFLIP(j) ((BTF_ISFLIPPED (j)) ? BTF_FLIP (j) : (j))
/* ========================================================================== */
/* === BTF version ========================================================== */
/* ========================================================================== */
/* All versions of BTF include these definitions.
* As an example, to test if the version you are using is 1.2 or later:
*
* if (BTF_VERSION >= BTF_VERSION_CODE (1,2)) ...
*
* This also works during compile-time:
*
* #if (BTF >= BTF_VERSION_CODE (1,2))
* printf ("This is version 1.2 or later\n") ;
* #else
* printf ("This is an early version\n") ;
* #endif
*/
#define BTF_DATE "Jun 1, 2012"
#define BTF_VERSION_CODE(main,sub) ((main) * 1000 + (sub))
#define BTF_MAIN_VERSION 1
#define BTF_SUB_VERSION 2
#define BTF_SUBSUB_VERSION 0
#define BTF_VERSION BTF_VERSION_CODE(BTF_MAIN_VERSION,BTF_SUB_VERSION)
#ifdef __cplusplus
}
#endif
#endif
|