#include "BSprivate.h"
/*+ BSrows_2_inode - Put the row numbers into the efficient parallel structure
Input Parameters:
. A - the original sparse matrix
. gnum - global numbering of the rows
. l_perm - local permutation of the rows
. l_iperm - inverse of the local permutation of the rows
. perm_row - permuted index into the original sparse matrix
. col_iA - i-node structure
. col_cA - clique structure
. key_arr - add to permutation (see BSperm_rows)
. i_number - numbering of the i-nodes
. i_distr - distribution of the numbering of the i-nodes
. procinfo - the usual processor stuff
Output Parameters:
. col_iA - updated to contain row numbers from A
Returns:
int
+*/
typedef struct __key_list {
int data;
struct __key_list *next;
} key_list;
typedef struct __row_list {
int count;
key_list *list;
} row_list;
#include "BStree.h"
#define DROP_KEY_IN_TREE(tree,keyval,row_val,row_len,row_num_ptr) \
{ \
int found99, dummy99=0; \
BStree_ptr node_ptr99; \
row_list *row_list_ptr99; \
key_list *tptr99; \
if (row_len[keyval] >= 1) { \
MY_INSERT_TREE_NODE(tree,row_val[keyval],found99,node_ptr99,dummy99); \
row_list_ptr99 = (row_list *) MY_GET_TREE_DATA(node_ptr99); \
if (found99) { \
row_list_ptr99->count++; \
} else { \
row_list_ptr99->count = 1; \
row_list_ptr99->list = NULL; \
} \
tptr99 = &(row_num_ptr[keyval]); \
tptr99->next = row_list_ptr99->list; \
tptr99->data = keyval; \
row_list_ptr99->list = tptr99; \
} \
}
int BSrows_2_inode(BSspmat *A, BSnumbering *gnum, BSpermutation *l_perm,
BSpermutation *l_iperm, BSsprow **perm_row, BSinode_list *col_iA,
BScl_2_inode *col_cA, BSkey_arr *key_arr, BSnumbering *i_number,
BSdistribution *i_distr, BSprocinfo *procinfo)
{
BStree tree;
BStree_ptr node_ptr;
row_list *row_list_ptr;
key_list *tptr;
int found, curkey;
int i, j, count;
BSsprow *row;
int *col_ptr;
int row_gnum;
int *row_len, *row_num, *row_ind, *row_val, *row_inum, *row_size;
key_list *row_num_ptr;
int cl_ind, in_ind, clique_len, inode_len;
BSinode *inode;
int cur_col, t_con, ind;
int done;
int curlen;
/* set up the row sorting stuff, recall that we use i-node to simplify */
MY_MALLOCN(row_len,(int *),sizeof(int)*(i_distr->max+1),2);
MY_MALLOCN(row_ind,(int *),sizeof(int)*(i_distr->max+1),3);
MY_MALLOCN(row_num_ptr,(key_list *),sizeof(key_list)*(i_distr->max+1),4);
MY_MALLOCN(row_num,(int *),sizeof(int)*(i_distr->max+1),4);
MY_MALLOCN(row_inum,(int *),sizeof(int)*(i_distr->max+1),5);
MY_MALLOCN(row_val,(int *),sizeof(int)*(i_distr->max+1),6);
MY_MALLOCN(row_size,(int *),sizeof(int)*(i_distr->max+1),7);
MY_INIT_TREE(tree,sizeof(row_list));
i = 0;
for (count=0;count<=i_distr->max;count++) {
row_inum[count] = i;
row_ind[count] = 0;
row_val[count] = key_arr->array[i_number->numbers[l_iperm->perm[i]]][0];
row_size[count] =
i_distr->distribution[i_number->numbers[l_iperm->perm[i]]];
row = perm_row[i];
col_ptr = row->col;
(*A->map->flocal2global)(1,&(l_iperm->perm[i]),&row_gnum,
procinfo,A->map); CHKERRN(0);
if(A->icc_storage) {
row_len[count] = -1;
for (j=0;j<row->length;j++) {
if (row_gnum == col_ptr[j]) {
row_len[count] = j+1;
break;
}
}
} else {
row_len[count] = row->length;
}
DROP_KEY_IN_TREE(tree,count,row_val,row_len,row_num_ptr);
i += row_size[count];
}
/* get the first list of row numbers */
MY_FIRST_IN_TREE(tree,node_ptr);
if (! IS_TREE_PTR_NULL(node_ptr)) {
done = FALSE;
row_list_ptr = (row_list *) MY_GET_TREE_DATA(node_ptr);
tptr = row_list_ptr->list;
curlen = row_list_ptr->count;
for (i=0;i<curlen;i++) {
row_num[i] = tptr->data;
tptr = tptr->next;
}
curkey = row_val[row_num[0]];
BSiheap_sort1(curlen,row_num,row_inum); CHKERRN(0);
} else {
done = TRUE;
}
/* end of getting row numbers */
/* initialize the clique and inode indices */
cl_ind = 0;
in_ind = 0;
clique_len = col_cA->d_mats[cl_ind].size;
/* now, place column numbers into inode structure */
/* we are doing 1 column/inode at a time */
/* we are keeping the rows sorted by two keys: 1)next col #, 2)row # */
/* row_num tells us what the sorted row number is and row_len */
/* tells how many columns are left in the row and row_ind tells */
/* us which col we are looking at within a row */
/* the only thing which is REALLY moved during a sort is row_num */
while (! done) {
if (col_iA->length <= in_ind) {
MY_SETERRCN(INODE_ERROR,"Too many inodes\n");
}
/* find the inode */
inode = &(col_iA->list[in_ind]);
inode_len = inode->num_cols;
/* count the number of connections to the inode */
cur_col = row_val[row_num[0]];
t_con = row_size[row_num[0]];
count = curlen; /* we get curlen from Msort_list */
for (i=1;i<curlen;i++) {
t_con+=row_size[row_num[i]];
}
inode->length = t_con;
/* Are we local or global? */
if (col_cA->proc[cl_ind] == procinfo->my_id) {
/* put the first part of the values that are in the clique */
/* nowhere, because we don't need indices for these values */
/* put the rest of the values into the inode */
if(A->icc_storage) {
i = 0;
t_con = 0;
while (t_con < clique_len) {
ind = row_num[i];
/* just ignore this part */
t_con += row_size[ind];
row_ind[ind] += inode_len;
row_len[ind] -= inode_len;
if (row_len[ind] > 0) {
row_val[ind] =
key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
[row_ind[ind]];
} else {
row_val[ind] = INT_MAX;
}
i++;
}
inode->length -= t_con;
/* allocate space in the inode */
MY_MALLOCN(inode->row_num,(int *),sizeof(int)*inode->length,8);
MY_MALLOCN(inode->nz,(FLOAT *),sizeof(FLOAT)*inode->length*
inode_len,9);
t_con = 0;
for (i=i;i<count;i++) {
ind = row_num[i];
/* insert all of the row inode into this column inode */
for (j=0;j<row_size[ind];j++) {
inode->row_num[t_con] = row_inum[ind]+j;
t_con++;
}
row_ind[ind] += inode_len;
row_len[ind] -= inode_len;
if (row_len[ind] > 0) {
row_val[ind] =
key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
[row_ind[ind]];
} else {
row_val[ind] = INT_MAX;
}
}
clique_len -= inode_len;
} else {
/* allocate space in the inode */
/* now the space allocated is a bit more than necessary (ILU) */
MY_MALLOCN(inode->row_num,(int *),sizeof(int)*inode->length,8);
MY_MALLOCN(inode->nz,(FLOAT *),sizeof(FLOAT)*inode->length*
inode_len,9);
t_con = 0;
inode->below_diag = 0;
for (i=0;i<count;i++) {
ind = row_num[i];
row_gnum = gnum->numbers[l_iperm->perm[row_inum[ind]]];
if (row_gnum < col_cA->g_offset[cl_ind]) {
inode->below_diag = t_con + row_size[ind];
}
if ((row_gnum >= col_cA->g_offset[cl_ind]) &
(row_gnum < col_cA->g_offset[cl_ind+1])) {
/* don't put in diag entry into inode->row_num (ILU) */
row_ind[ind] += inode_len;
row_len[ind] -= inode_len;
if (row_len[ind] > 0) {
row_val[ind] =
key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
[row_ind[ind]];
} else {
row_val[ind] = INT_MAX;
}
inode->length -= row_size[ind];
} else {
/* insert all of the row inode into this column inode */
for (j=0;j<row_size[ind];j++) {
inode->row_num[t_con] = row_inum[ind]+j;
t_con++;
}
row_ind[ind] += inode_len;
row_len[ind] -= inode_len;
if (row_len[ind] > 0) {
row_val[ind] =
key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
[row_ind[ind]];
} else {
row_val[ind] = INT_MAX;
}
}
}
clique_len -= inode_len;
}
} else {
/* allocate space in the inode */
MY_MALLOCN(inode->row_num,(int *),sizeof(int)*inode->length,10);
MY_MALLOCN(inode->nz,(FLOAT *),sizeof(FLOAT)*inode->length*
inode_len,11);
/* put all values into the inode, (no non-local cliques) */
t_con = 0;
inode->below_diag = 0;
for (i=0;i<count;i++) {
ind = row_num[i];
row_gnum = gnum->numbers[l_iperm->perm[row_inum[ind]]];
if (row_gnum < col_cA->g_offset[cl_ind]) {
inode->below_diag = t_con + row_size[ind];
}
/* insert all of the row inode into this column inode */
for (j=0;j<row_size[ind];j++) {
inode->row_num[t_con] = row_inum[ind]+j;
t_con++;
}
row_ind[ind] += inode_len;
row_len[ind] -= inode_len;
if (row_len[ind] > 0) {
row_val[ind] =
key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
[row_ind[ind]];
} else {
row_val[ind] = INT_MAX;
}
}
}
/* get the next list of row numbers */
/* free up the current list of row numbers */
for (i=0;i<curlen;i++) {
DROP_KEY_IN_TREE(tree,row_num[i],row_val,row_len,row_num_ptr);
}
MY_SEARCH_TREE(tree,curkey,found,node_ptr);
MY_NEXT_IN_TREE(node_ptr);
if (! IS_TREE_PTR_NULL(node_ptr)) {
done = FALSE;
row_list_ptr = (row_list *) MY_GET_TREE_DATA(node_ptr);
tptr = row_list_ptr->list;
curlen = row_list_ptr->count;
for (i=0;i<curlen;i++) {
row_num[i] = tptr->data;
tptr = tptr->next;
}
curkey = row_val[row_num[0]];
BSiheap_sort1(curlen,row_num,row_inum); CHKERRN(0);
} else {
done = TRUE;
}
/* end of getting row numbers */
/* update clique/inode indices */
in_ind++;
if (in_ind >= col_cA->inode_index[cl_ind+1]) {
cl_ind++;
clique_len = col_cA->d_mats[cl_ind].size;
}
}
/* free up sorting vectors */
MY_FREE_TREE(tree);
MY_FREEN(row_len);
MY_FREEN(row_ind);
MY_FREEN(row_num);
MY_FREEN(row_num_ptr);
MY_FREEN(row_inum);
MY_FREEN(row_val);
MY_FREEN(row_size);
return(0);
}
syntax highlighted by Code2HTML, v. 0.9.1