#include "BSprivate.h"
/*@ BSmain_perm - Permute the matrix for efficient parallel execution
Input Parameters:
. procinfo - the usual processor context information
. A - the sparse matrix
Returns:
the sparse matrix permuted into an efficient structure
Notes:
$ (1) The sparse matrix must be symmetric in structure
$ (2) The graph associated with the sparse matrix must be connected
$ (3) max_inode_size and max_clique_size should usually be set to
$ INT_MAX (they are kept in the context)
$ (4) see the manual for more details on what algorithms BSmain_perm uses
$ (5) the context variable "retain" will indicate whether or not
$ some extra data should be kept around to allow for fast permutation
$ of a matrix with the same structure in the future
@*/
BSpar_mat *BSmain_perm(BSprocinfo *procinfo, BSspmat *A)
{
BSpar_mat *pA;
BSnumbering *inode_number;
BSdistribution *inode_distr;
BSpermutation *inode_perm;
BSnumbering *inode_row;
BSnumbering *clique_number;
BSdistribution *clique_distr;
BSpermutation *clique_perm;
BSnumbering *color_number;
BSdistribution *color_distr;
BSpermutation *color_perm;
BSspmat *iA;
BSspmat *cA;
BSnumbering *color_offset;
BSnumbering *color_base;
BSdistribution *new_clique_distr;
BSdistribution *new_color_distr;
BSnumbering *clique_gnum;
BSnumbering *inode_gnum;
BSnumbering *row_gnum;
BScl_2_inode *col_cA;
BSinode_list *col_iA;
BSnumbering *color_2_cl;
BSkey_arr *key_arr;
BSsprow **perm_rows;
BSpermutation *g_perm, *g_iperm;
int max_gcolors;
int max_row_len;
int local_num_inodes, global_num_inodes;
int local_num_cliques, global_num_cliques;
int num_colors;
int ierr;
/* *************************************************************** */
/* BEGIN SECTION: */
/* Find the various permutations and contracted graphs */
/* *************************************************************** */
/* first check that matrix symmetry property and storage will work */
if((!A->symmetric)&&(A->icc_storage)) {
MY_SETERRCN(SYM_ERROR,"Attempt to store nonsymmetric matrix in ICC structure\n");
}
/* check rows for consistency */
if (procinfo->error_check) {
BSrow_err_check(A,procinfo); CHKERRN(0);
}
/* now get an i-node numbering */
MLOG_ELM(procinfo->procset);
inode_number = BSfnd_inode(A,procinfo->max_inode_size,procinfo); CHKERRN(0);
inode_distr = BSnum2distr(inode_number); CHKERRN(0);
inode_perm = BSnum2perm(inode_number,inode_distr); CHKERRN(0);
inode_row = BSlow2high(A,inode_number,inode_distr,procinfo); CHKERRN(0);
if (procinfo->single) {
iA = A;
} else {
iA = BSdo_contract(A,inode_number,inode_perm,procinfo,TRUE); CHKERRN(0);
}
MLOG_IT(INODE);
local_num_inodes = iA->num_rows;
global_num_inodes = iA->global_num_rows;
if ((procinfo->print) && (PSISROOT(procinfo))) {
printf("************** Blocksolve Reordering Info *****************\n");
printf("o Inode graph size is %d\n",iA->global_num_rows);
}
/* check rows for consistency */
if (procinfo->error_check) {
BSrow_err_check(iA,procinfo); CHKERRN(0);
}
/* now get a clique numbering */
MLOG_ELM(procinfo->procset);
clique_number = BSfnd_clique(iA,procinfo->max_clique_size,
inode_distr->distribution,procinfo); CHKERRN(0);
clique_distr = BSnum2distr(clique_number); CHKERRN(0);
clique_perm = BSnum2perm(clique_number,clique_distr); CHKERRN(0);
if (procinfo->single) {
cA = A;
} else {
cA = BSdo_contract(iA,clique_number,clique_perm,procinfo,FALSE);
CHKERRN(0);
}
MLOG_IT(CLIQUE);
local_num_cliques = cA->num_rows;
global_num_cliques = cA->global_num_rows;
if ((procinfo->print) && (PSISROOT(procinfo))) {
printf("o Clique graph size is %d\n",cA->global_num_rows);
}
/* find weights */
new_clique_distr = BSfold_distr(clique_distr,inode_distr,clique_number);
CHKERRN(0);
/* now do the coloring */
BSrem_diag(cA); CHKERRN(0);
color_number = BSalloc_numbering(cA->num_rows); CHKERRN(0);
BSx_color(color_number->numbers,cA,procinfo,&max_gcolors,
procinfo->coloring_type); CHKERRN(0);
color_distr = BSnum2distr(color_number); CHKERRN(0);
color_perm = BSnum2perm(color_number,color_distr); CHKERRN(0);
BSins_diag(cA); CHKERRN(0);
/* check rows for consistency */
if (procinfo->error_check) {
BSrow_err_check(cA,procinfo); CHKERRN(0);
}
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
/* *************************************************************** */
/* BEGIN SECTION: */
/* Find global row numbers */
/* *************************************************************** */
MLOG_ELM(procinfo->procset);
new_color_distr = BSfold_distr(color_distr,new_clique_distr,color_number);
CHKERRN(0);
/* find the new global offsets for the colors */
MY_MALLOCN(color_offset,(BSnumbering *),sizeof(BSnumbering),1);
color_offset->length = BSoffset(new_color_distr->max+1,
new_color_distr->distribution,&(color_offset->numbers),procinfo);
CHKERRN(0);
num_colors = color_offset->length;
if ((procinfo->print) && (PSISROOT(procinfo))) {
printf("o Number of colors is %d\n",color_offset->length);
}
/* find the new global base addresses for the colors */
/* this is the same on every processors */
color_base = BSbase(new_color_distr,procinfo); CHKERRN(0);
/* find the new global offsets for the cliques */
clique_gnum = BSoff_gnum(color_offset,color_number,new_clique_distr);
CHKERRN(0);
/* find the new global offsets for the inodes */
inode_gnum = BSoff_gnum(clique_gnum,clique_number,inode_distr); CHKERRN(0);
/* find the new global addresses for the rows */
row_gnum = BSoff_gnum(inode_gnum,inode_number,NULL); CHKERRN(0);
/* get permutation based on new global addresses */
/* also get a permuted version of the rows */
g_perm = BSglobal_perm(row_gnum); CHKERRN(0);
g_iperm = BSalloc_permutation(g_perm->length); CHKERRN(0);
BSperm2iperm(g_perm,g_iperm); CHKERRN(0);
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
/* *************************************************************** */
/* BEGIN SECTION: */
/* Propagate the permutation until the row level */
/* *************************************************************** */
/* get the transpose structure of the cliques */
col_cA = BStrans_perm_cl(cA,clique_gnum,procinfo); CHKERRN(0);
/* get the tranpose structure of the inodes */
col_iA = BStrans_perm_in(iA,inode_gnum,inode_row,inode_distr,
procinfo); CHKERRN(0);
/* set the pointers of the clique structure into the inode structure */
BSclique_2_inode(A,col_cA,col_iA,procinfo); CHKERRN(0);
/* set the pointers of the color structure into the clique structure */
color_2_cl = BScolor_2_clique(color_base,col_cA); CHKERRN(0);
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
/* *************************************************************** */
/* BEGIN SECTION: */
/* Permute the nonzeros at the row level and sort them */
/* Remember to unsort them */
/* *************************************************************** */
key_arr = BSperm_rows(A,row_gnum,inode_perm,inode_distr,procinfo,TRUE,
&max_row_len); CHKERRN(0);
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
/* *************************************************************** */
/* BEGIN SECTION: */
/* Put the row numbers into the transposed inode structure */
/* *************************************************************** */
perm_rows = BSrow_perm(A,g_iperm); CHKERRN(0);
ierr = BSrows_2_inode(A,row_gnum,g_perm,g_iperm,perm_rows,col_iA,
col_cA,key_arr,inode_number,inode_distr,procinfo); CHKERRN(0);
BSfree_key_arr(key_arr); CHKERRN(0);
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
/* *************************************************************** */
/* BEGIN SECTION: */
/* Put the numeric values into the transposed inode structure */
/* *************************************************************** */
BSnz_2_inode(A,perm_rows,col_iA,col_cA,procinfo); CHKERRN(0);
MY_FREEN(perm_rows);
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
/* *************************************************************** */
/* BEGIN SECTION: */
/* Unsort the rows to original condition */
/* *************************************************************** */
BSsort_rows(A,inode_perm,inode_distr,max_row_len); CHKERRN(0);
/* *************************************************************** */
/* END SECTION: */
/* *************************************************************** */
BSfree_numbering(inode_number); CHKERRN(0);
BSfree_numbering(inode_row); CHKERRN(0);
BSfree_numbering(clique_number); CHKERRN(0);
BSfree_distribution(clique_distr); CHKERRN(0);
BSfree_permutation(clique_perm); CHKERRN(0);
BSfree_numbering(color_number); CHKERRN(0);
BSfree_distribution(color_distr); CHKERRN(0);
BSfree_permutation(color_perm); CHKERRN(0);
if (!procinfo->single) {
BSfree_spmat(iA);
CHKERRN(0);
}
if (!procinfo->single) {
BSfree_spmat(cA);
CHKERRN(0);
}
BSfree_numbering(color_offset); CHKERRN(0);
BSfree_numbering(color_base); CHKERRN(0);
BSfree_distribution(new_clique_distr); CHKERRN(0);
BSfree_distribution(new_color_distr); CHKERRN(0);
BSfree_numbering(clique_gnum); CHKERRN(0);
BSfree_numbering(inode_gnum); CHKERRN(0);
/* set up return structure */
MY_MALLOCN(pA,(BSpar_mat *),sizeof(BSpar_mat),2);
pA->num_rows = A->num_rows;
pA->global_num_rows = A->global_num_rows;
pA->local_num_inodes = local_num_inodes;
pA->global_num_inodes = global_num_inodes;
pA->local_num_cliques = local_num_cliques;
pA->global_num_cliques = global_num_cliques;
pA->num_colors = num_colors;
pA->symmetric = A->symmetric;
pA->icc_storage = A->icc_storage;
pA->perm = g_perm;
pA->inv_perm = g_iperm;
pA->color2clique = color_2_cl;
pA->clique2inode = col_cA;
pA->inodes = col_iA;
pA->global_row_num = row_gnum;
pA->map = A->map;
/* allocate space for and get the diagonals */
MY_MALLOCN(pA->diag,(FLOAT *),pA->num_rows*sizeof(FLOAT),3);
BSget_diag(pA,pA->diag,procinfo); CHKERRN(0);
pA->save_diag = pA->diag;
pA->scale_diag = NULL;
if (procinfo->retain) {
MY_MALLOCN(pA->reperm,(BSreperm *),sizeof(BSreperm),4);
pA->reperm->inode_perm = inode_perm;
pA->reperm->inode_distr = inode_distr;
} else {
pA->reperm = NULL;
BSfree_distribution(inode_distr); CHKERRN(0);
BSfree_permutation(inode_perm); CHKERRN(0);
}
/* go over and patch up inode structure with original inode numbers */
BSorig_inode(pA,procinfo); CHKERRN(0);
pA->local_nnz = BScount_nz(pA,procinfo); CHKERRN(0);
pA->max_local_row_length = max_row_len;
MLOG_IT(PERMUTE);
return(pA);
}
syntax highlighted by Code2HTML, v. 0.9.1