externals/SuiteSparse/LDL/ldl_di.c
/* The input to this routine is a sparse matrix A, stored in column form, and
 * an optional permutation P.  The output is the elimination tree
 * and the number of nonzeros in each column of L.  Parent [i] = k if k is the
 * parent of i in the tree.  The Parent array is required by ldl_numeric.
 * Lnz [k] gives the number of nonzeros in the kth column of L, excluding the
 * diagonal.
 *
 * One workspace vector (Flag) of size n is required.
 *
 * If P is NULL, then it is ignored.  The factorization will be LDL' = A.
 * Pinv is not computed.  In this case, neither P nor Pinv are required by
 * ldl_numeric.
 *
 * If P is not NULL, then it is assumed to be a valid permutation.  If
 * row and column j of A is the kth pivot, the P [k] = j.  The factorization
 * will be LDL' = PAP', or A (p,p) in MATLAB notation.  The inverse permutation
 * Pinv is computed, where Pinv [j] = k if P [k] = j.  In this case, both P
 * and Pinv are required as inputs to ldl_numeric.
 *
 * The floating-point operation count of the subsequent call to ldl_numeric
 * is not returned, but could be computed after ldl_symbolic is done.  It is
 * the sum of (Lnz [k]) * (Lnz [k] + 2) for k = 0 to n-1.
 */
The input to this routine is a sparse matrix A, stored in column form, and
an optional permutation P.  The output is the elimination tree
and the number of nonzeros in each column of L.  Parent [i] = k if k is the
parent of i in the tree.  The Parent array is required by ldl_numeric.
Lnz [k] gives the number of nonzeros in the kth column of L, excluding the
diagonal.

One workspace vector (Flag) of size n is required.

If P is NULL, then it is ignored.  The factorization will be LDL' = A.
Pinv is not computed.  In this case, neither P nor Pinv are required by
ldl_numeric.

If P is not NULL, then it is assumed to be a valid permutation.  If
row and column j of A is the kth pivot, the P [k] = j.  The factorization
will be LDL' = PAP', or A (p,p) in MATLAB notation.  The inverse permutation
Pinv is computed, where Pinv [j] = k if P [k] = j.  In this case, both P
and Pinv are required as inputs to ldl_numeric.

The floating-point operation count of the subsequent call to ldl_numeric
is not returned, but could be computed after ldl_symbolic is done.
The input to this routine is a sparse matrix A stored in column form and an optional permutation P . The output is the elimination tree and the number of nonzeros in each column of L . Parent [ i ] = k if k is the parent of i in the tree . The Parent array is required by ldl_numeric . Lnz [ k ] gives the number of nonzeros in the kth column of L excluding the diagonal . One workspace vector ( Flag ) of size n is required . If P is NULL then it is ignored . The factorization will be LDL ' = A . Pinv is not computed . In this case neither P nor Pinv are required by ldl_numeric . If P is not NULL then it is assumed to be a valid permutation . If row and column j of A is the kth pivot the P [ k ] = j . The factorization will be LDL ' = PAP ' or A ( p p ) in MATLAB notation . The inverse permutation Pinv is computed where Pinv [ j ] = k if P [ k ] = j . In this case both P and Pinv are required as inputs to ldl_numeric . The floating - point operation count of the subsequent call to ldl_numeric is not returned but could be computed after ldl_symbolic is done .
void LDL_symbolic
(
    LDL_int n,		
    LDL_int Ap [ ],	
    LDL_int Ai [ ],	
    LDL_int Lp [ ],	
    LDL_int Parent [ ],	
    LDL_int Lnz [ ],	
    LDL_int Flag [ ],	
    LDL_int P [ ],	
    LDL_int Pinv [ ]	
)
{
    LDL_int i, k, p, kk, p2 ;
    if (P)
    {
	for (k = 0 ; k < n ; k++)
	{
	    Pinv [P [k]] = k ;
	}
    }
    for (k = 0 ; k < n ; k++)
    {
	Parent [k] = -1 ;	    
	Flag [k] = k ;		    
	Lnz [k] = 0 ;		    
	kk = (P) ? (P [k]) : (k) ;  
	p2 = Ap [kk+1] ;
	for (p = Ap [kk] ; p < p2 ; p++)
	{
	    i = (Pinv) ? (Pinv [Ai [p]]) : (Ai [p]) ;
	    if (i < k)
	    {
		for ( ; Flag [i] != k ; i = Parent [i])
		{
		    if (Parent [i] == -1) Parent [i] = k ;
		    Lnz [i]++ ;				
		    Flag [i] = k ;			
		}
	    }
	}
    }
    Lp [0] = 0 ;
    for (k = 0 ; k < n ; k++)
    {
	Lp [k+1] = Lp [k] + Lnz [k] ;
    }
}
void LDL_symbolic ( LDL_int n , LDL_int Ap [ ] , LDL_int Ai [ ] , LDL_int Lp [ ] , LDL_int Parent [ ] , LDL_int Lnz [ ] , LDL_int Flag [ ] , LDL_int P [ ] , LDL_int Pinv [ ] ) { LDL_int i , k , p , kk , p2 ; if ( P ) { for ( k = 0 ; k < n ; k ++ ) { Pinv [ P [ k ] ] = k ; } } for ( k = 0 ; k < n ; k ++ ) { Parent [ k ] = -1 ; Flag [ k ] = k ; Lnz [ k ] = 0 ; kk = ( P ) ? ( P [ k ] ) : ( k ) ; p2 = Ap [ kk + 1 ] ; for ( p = Ap [ kk ] ; p < p2 ; p ++ ) { i = ( Pinv ) ? ( Pinv [ Ai [ p ] ] ) : ( Ai [ p ] ) ; if ( i < k ) { for ( ; Flag [ i ] != k ; i = Parent [ i ] ) { if ( Parent [ i ] == -1 ) Parent [ i ] = k ; Lnz [ i ] ++ ; Flag [ i ] = k ; } } } } Lp [ 0 ] = 0 ; for ( k = 0 ; k < n ; k ++ ) { Lp [ k + 1 ] = Lp [ k ] + Lnz [ k ] ; } }
The input to this routine is a sparse matrix A, stored in column form, and
 an optional permutation P.  The output is the elimination tree
 and the number of nonzeros in each column of L.  Parent [i] = k if k is the
 parent of i in the tree.
The input to this routine is a sparse matrix A stored in column form and an optional permutation P . The output is the elimination tree and the number of nonzeros in each column of L . Parent [ i ] = k if k is the parent of i in the tree .
/* A and L are n-by-n, where n >= 0 */ /* input of size n+1, not modified */ /* input of size nz=Ap[n], not modified */ /* output of size n+1, not defined on input */ /* output of size n, not defined on input */ /* output of size n, not defined on input */ /* workspace of size n, not defn. on input or output */ /* optional input of size n */ /* optional output of size n (used if P is not NULL) */ /* If P is present then compute Pinv, the inverse of P */ /* L(k,:) pattern: all nodes reachable in etree from nz in A(0:k-1,k) */ /* parent of k is not yet known */ /* mark node k as visited */ /* count of nonzeros in column k of L */ /* kth original, or permuted, column */ /* A (i,k) is nonzero (original or permuted A) */ /* follow path from i to root of etree, stop at flagged node */ /* find parent of i if not yet determined */ /* L (k,i) is nonzero */ /* mark i as visited */ /* construct Lp index array from Lnz column counts */