1 #define PETSCKSP_DLL 2 3 /*************************************xxt.c************************************ 4 Module Name: xxt 5 Module Info: 6 7 author: Henry M. Tufo III 8 e-mail: hmt@asci.uchicago.edu 9 contact: 10 +--------------------------------+--------------------------------+ 11 |MCS Division - Building 221 |Department of Computer Science | 12 |Argonne National Laboratory |Ryerson 152 | 13 |9700 S. Cass Avenue |The University of Chicago | 14 |Argonne, IL 60439 |Chicago, IL 60637 | 15 |(630) 252-5354/5986 ph/fx |(773) 702-6019/8487 ph/fx | 16 +--------------------------------+--------------------------------+ 17 18 Last Modification: 3.20.01 19 **************************************xxt.c***********************************/ 20 21 22 /*************************************xxt.c************************************ 23 NOTES ON USAGE: 24 25 **************************************xxt.c***********************************/ 26 #include "src/ksp/pc/impls/tfs/tfs.h" 27 28 #define LEFT -1 29 #define RIGHT 1 30 #define BOTH 0 31 #define MAX_FORTRAN_HANDLES 10 32 33 typedef struct xxt_solver_info { 34 int n, m, n_global, m_global; 35 int nnz, max_nnz, msg_buf_sz; 36 int *nsep, *lnsep, *fo, nfo, *stages; 37 int *col_sz, *col_indices; 38 PetscScalar **col_vals, *x, *solve_uu, *solve_w; 39 int nsolves; 40 PetscScalar tot_solve_time; 41 } xxt_info; 42 43 typedef struct matvec_info { 44 int n, m, n_global, m_global; 45 int *local2global; 46 gs_ADT gs_handle; 47 PetscErrorCode (*matvec)(struct matvec_info*,PetscScalar*,PetscScalar*); 48 void *grid_data; 49 } mv_info; 50 51 struct xxt_CDT{ 52 int id; 53 int ns; 54 int level; 55 xxt_info *info; 56 mv_info *mvi; 57 }; 58 59 static int n_xxt=0; 60 static int n_xxt_handles=0; 61 62 /* prototypes */ 63 static PetscErrorCode do_xxt_solve(xxt_ADT xxt_handle, PetscScalar *rhs); 64 static PetscErrorCode check_init(void); 65 static PetscErrorCode check_handle(xxt_ADT xxt_handle); 66 static PetscErrorCode det_separators(xxt_ADT xxt_handle); 67 static PetscErrorCode do_matvec(mv_info *A, PetscScalar *v, PetscScalar *u); 68 static int xxt_generate(xxt_ADT xxt_handle); 69 static int do_xxt_factor(xxt_ADT xxt_handle); 70 static mv_info *set_mvi(int *local2global, int n, int m, void *matvec, void *grid_data); 71 72 73 74 /*************************************xxt.c************************************ 75 Function: XXT_new() 76 77 Input : 78 Output: 79 Return: 80 Description: 81 **************************************xxt.c***********************************/ 82 xxt_ADT 83 XXT_new(void) 84 { 85 xxt_ADT xxt_handle; 86 87 88 89 /* rolling count on n_xxt ... pot. problem here */ 90 n_xxt_handles++; 91 xxt_handle = (xxt_ADT)malloc(sizeof(struct xxt_CDT)); 92 xxt_handle->id = ++n_xxt; 93 xxt_handle->info = NULL; xxt_handle->mvi = NULL; 94 95 return(xxt_handle); 96 } 97 98 99 /*************************************xxt.c************************************ 100 Function: XXT_factor() 101 102 Input : 103 Output: 104 Return: 105 Description: 106 **************************************xxt.c***********************************/ 107 int 108 XXT_factor(xxt_ADT xxt_handle, /* prev. allocated xxt handle */ 109 int *local2global, /* global column mapping */ 110 int n, /* local num rows */ 111 int m, /* local num cols */ 112 void *matvec, /* b_loc=A_local.x_loc */ 113 void *grid_data /* grid data for matvec */ 114 ) 115 { 116 check_init(); 117 check_handle(xxt_handle); 118 119 /* only 2^k for now and all nodes participating */ 120 if ((1<<(xxt_handle->level=i_log2_num_nodes))!=num_nodes) 121 {error_msg_fatal("only 2^k for now and MPI_COMM_WORLD!!! %d != %d\n",1<<i_log2_num_nodes,num_nodes);} 122 123 /* space for X info */ 124 xxt_handle->info = (xxt_info*)malloc(sizeof(xxt_info)); 125 126 /* set up matvec handles */ 127 xxt_handle->mvi = set_mvi(local2global, n, m, matvec, grid_data); 128 129 /* matrix is assumed to be of full rank */ 130 /* LATER we can reset to indicate rank def. */ 131 xxt_handle->ns=0; 132 133 /* determine separators and generate firing order - NB xxt info set here */ 134 det_separators(xxt_handle); 135 136 return(do_xxt_factor(xxt_handle)); 137 } 138 139 140 /*************************************xxt.c************************************ 141 Function: XXT_solve 142 143 Input : 144 Output: 145 Return: 146 Description: 147 **************************************xxt.c***********************************/ 148 int 149 XXT_solve(xxt_ADT xxt_handle, double *x, double *b) 150 { 151 152 check_init(); 153 check_handle(xxt_handle); 154 155 /* need to copy b into x? */ 156 if (b) 157 {rvec_copy(x,b,xxt_handle->mvi->n);} 158 do_xxt_solve(xxt_handle,x); 159 160 return(0); 161 } 162 163 164 /*************************************xxt.c************************************ 165 Function: XXT_free() 166 167 Input : 168 Output: 169 Return: 170 Description: 171 **************************************xxt.c***********************************/ 172 int 173 XXT_free(xxt_ADT xxt_handle) 174 { 175 176 check_init(); 177 check_handle(xxt_handle); 178 n_xxt_handles--; 179 180 free(xxt_handle->info->nsep); 181 free(xxt_handle->info->lnsep); 182 free(xxt_handle->info->fo); 183 free(xxt_handle->info->stages); 184 free(xxt_handle->info->solve_uu); 185 free(xxt_handle->info->solve_w); 186 free(xxt_handle->info->x); 187 free(xxt_handle->info->col_vals); 188 free(xxt_handle->info->col_sz); 189 free(xxt_handle->info->col_indices); 190 free(xxt_handle->info); 191 free(xxt_handle->mvi->local2global); 192 gs_free(xxt_handle->mvi->gs_handle); 193 free(xxt_handle->mvi); 194 free(xxt_handle); 195 196 197 198 /* if the check fails we nuke */ 199 /* if NULL pointer passed to free we nuke */ 200 /* if the calls to free fail that's not my problem */ 201 return(0); 202 } 203 204 205 206 /*************************************xxt.c************************************ 207 Function: 208 209 Input : 210 Output: 211 Return: 212 Description: 213 **************************************xxt.c***********************************/ 214 int 215 XXT_stats(xxt_ADT xxt_handle) 216 { 217 int op[] = {NON_UNIFORM,GL_MIN,GL_MAX,GL_ADD,GL_MIN,GL_MAX,GL_ADD,GL_MIN,GL_MAX,GL_ADD}; 218 int fop[] = {NON_UNIFORM,GL_MIN,GL_MAX,GL_ADD}; 219 int vals[9], work[9]; 220 PetscScalar fvals[3], fwork[3]; 221 222 223 224 check_init(); 225 check_handle(xxt_handle); 226 227 /* if factorization not done there are no stats */ 228 if (!xxt_handle->info||!xxt_handle->mvi) 229 { 230 if (!my_id) 231 {printf("XXT_stats() :: no stats available!\n");} 232 return 1; 233 } 234 235 vals[0]=vals[1]=vals[2]=xxt_handle->info->nnz; 236 vals[3]=vals[4]=vals[5]=xxt_handle->mvi->n; 237 vals[6]=vals[7]=vals[8]=xxt_handle->info->msg_buf_sz; 238 giop(vals,work,sizeof(op)/sizeof(op[0])-1,op); 239 240 fvals[0]=fvals[1]=fvals[2] 241 =xxt_handle->info->tot_solve_time/xxt_handle->info->nsolves++; 242 grop(fvals,fwork,sizeof(fop)/sizeof(fop[0])-1,fop); 243 244 if (!my_id) 245 { 246 printf("%d :: min xxt_nnz=%d\n",my_id,vals[0]); 247 printf("%d :: max xxt_nnz=%d\n",my_id,vals[1]); 248 printf("%d :: avg xxt_nnz=%g\n",my_id,1.0*vals[2]/num_nodes); 249 printf("%d :: tot xxt_nnz=%d\n",my_id,vals[2]); 250 printf("%d :: xxt C(2d) =%g\n",my_id,vals[2]/(pow(1.0*vals[5],1.5))); 251 printf("%d :: xxt C(3d) =%g\n",my_id,vals[2]/(pow(1.0*vals[5],1.6667))); 252 printf("%d :: min xxt_n =%d\n",my_id,vals[3]); 253 printf("%d :: max xxt_n =%d\n",my_id,vals[4]); 254 printf("%d :: avg xxt_n =%g\n",my_id,1.0*vals[5]/num_nodes); 255 printf("%d :: tot xxt_n =%d\n",my_id,vals[5]); 256 printf("%d :: min xxt_buf=%d\n",my_id,vals[6]); 257 printf("%d :: max xxt_buf=%d\n",my_id,vals[7]); 258 printf("%d :: avg xxt_buf=%g\n",my_id,1.0*vals[8]/num_nodes); 259 printf("%d :: min xxt_slv=%g\n",my_id,fvals[0]); 260 printf("%d :: max xxt_slv=%g\n",my_id,fvals[1]); 261 printf("%d :: avg xxt_slv=%g\n",my_id,fvals[2]/num_nodes); 262 } 263 264 return(0); 265 } 266 267 268 /*************************************xxt.c************************************ 269 Function: do_xxt_factor 270 271 Input : 272 Output: 273 Return: 274 Description: get A_local, local portion of global coarse matrix which 275 is a row dist. nxm matrix w/ n<m. 276 o my_ml holds address of ML struct associated w/A_local and coarse grid 277 o local2global holds global number of column i (i=0,...,m-1) 278 o local2global holds global number of row i (i=0,...,n-1) 279 o mylocmatvec performs A_local . vec_local (note that gs is performed using 280 gs_init/gop). 281 282 mylocmatvec = my_ml->Amat[grid_tag].matvec->external; 283 mylocmatvec (void :: void *data, double *in, double *out) 284 **************************************xxt.c***********************************/ 285 static 286 int 287 do_xxt_factor(xxt_ADT xxt_handle) 288 { 289 int flag; 290 291 292 flag=xxt_generate(xxt_handle); 293 294 return(flag); 295 } 296 297 298 /*************************************xxt.c************************************ 299 Function: 300 301 Input : 302 Output: 303 Return: 304 Description: 305 **************************************xxt.c***********************************/ 306 static 307 int 308 xxt_generate(xxt_ADT xxt_handle) 309 { 310 int i,j,k,idex; 311 int dim, col; 312 PetscScalar *u, *uu, *v, *z, *w, alpha, alpha_w; 313 int *segs; 314 int op[] = {GL_ADD,0}; 315 int off, len; 316 PetscScalar *x_ptr; 317 int *iptr, flag; 318 int start=0, end, work; 319 int op2[] = {GL_MIN,0}; 320 gs_ADT gs_handle; 321 int *nsep, *lnsep, *fo; 322 int a_n=xxt_handle->mvi->n; 323 int a_m=xxt_handle->mvi->m; 324 int *a_local2global=xxt_handle->mvi->local2global; 325 int level; 326 int xxt_nnz=0, xxt_max_nnz=0; 327 int n, m; 328 int *col_sz, *col_indices, *stages; 329 PetscScalar **col_vals, *x; 330 int n_global; 331 int xxt_zero_nnz=0; 332 int xxt_zero_nnz_0=0; 333 PetscBLASInt i1 = 1; 334 PetscScalar dm1 = -1.0; 335 336 n=xxt_handle->mvi->n; 337 nsep=xxt_handle->info->nsep; 338 lnsep=xxt_handle->info->lnsep; 339 fo=xxt_handle->info->fo; 340 end=lnsep[0]; 341 level=xxt_handle->level; 342 gs_handle=xxt_handle->mvi->gs_handle; 343 344 /* is there a null space? */ 345 /* LATER add in ability to detect null space by checking alpha */ 346 for (i=0, j=0; i<=level; i++) 347 {j+=nsep[i];} 348 349 m = j-xxt_handle->ns; 350 if (m!=j) 351 {printf("xxt_generate() :: null space exists %d %d %d\n",m,j,xxt_handle->ns);} 352 353 /* get and initialize storage for x local */ 354 /* note that x local is nxm and stored by columns */ 355 col_sz = (int*) malloc(m*sizeof(PetscInt)); 356 col_indices = (int*) malloc((2*m+1)*sizeof(int)); 357 col_vals = (PetscScalar **) malloc(m*sizeof(PetscScalar *)); 358 for (i=j=0; i<m; i++, j+=2) 359 { 360 col_indices[j]=col_indices[j+1]=col_sz[i]=-1; 361 col_vals[i] = NULL; 362 } 363 col_indices[j]=-1; 364 365 /* size of separators for each sub-hc working from bottom of tree to top */ 366 /* this looks like nsep[]=segments */ 367 stages = (int*) malloc((level+1)*sizeof(PetscInt)); 368 segs = (int*) malloc((level+1)*sizeof(PetscInt)); 369 ivec_zero(stages,level+1); 370 ivec_copy(segs,nsep,level+1); 371 for (i=0; i<level; i++) 372 {segs[i+1] += segs[i];} 373 stages[0] = segs[0]; 374 375 /* temporary vectors */ 376 u = (PetscScalar *) malloc(n*sizeof(PetscScalar)); 377 z = (PetscScalar *) malloc(n*sizeof(PetscScalar)); 378 v = (PetscScalar *) malloc(a_m*sizeof(PetscScalar)); 379 uu = (PetscScalar *) malloc(m*sizeof(PetscScalar)); 380 w = (PetscScalar *) malloc(m*sizeof(PetscScalar)); 381 382 /* extra nnz due to replication of vertices across separators */ 383 for (i=1, j=0; i<=level; i++) 384 {j+=nsep[i];} 385 386 /* storage for sparse x values */ 387 n_global = xxt_handle->info->n_global; 388 xxt_max_nnz = (int)(2.5*pow(1.0*n_global,1.6667) + j*n/2)/num_nodes; 389 x = (PetscScalar *) malloc(xxt_max_nnz*sizeof(PetscScalar)); 390 xxt_nnz = 0; 391 392 /* LATER - can embed next sep to fire in gs */ 393 /* time to make the donuts - generate X factor */ 394 for (dim=i=j=0;i<m;i++) 395 { 396 /* time to move to the next level? */ 397 while (i==segs[dim]) 398 { 399 if (dim==level) 400 {error_msg_fatal("dim about to exceed level\n"); break;} 401 402 stages[dim++]=i; 403 end+=lnsep[dim]; 404 } 405 stages[dim]=i; 406 407 /* which column are we firing? */ 408 /* i.e. set v_l */ 409 /* use new seps and do global min across hc to determine which one to fire */ 410 (start<end) ? (col=fo[start]) : (col=INT_MAX); 411 giop_hc(&col,&work,1,op2,dim); 412 413 /* shouldn't need this */ 414 if (col==INT_MAX) 415 { 416 error_msg_warning("hey ... col==INT_MAX??\n"); 417 continue; 418 } 419 420 /* do I own it? I should */ 421 rvec_zero(v ,a_m); 422 if (col==fo[start]) 423 { 424 start++; 425 idex=ivec_linear_search(col, a_local2global, a_n); 426 if (idex!=-1) 427 {v[idex] = 1.0; j++;} 428 else 429 {error_msg_fatal("NOT FOUND!\n");} 430 } 431 else 432 { 433 idex=ivec_linear_search(col, a_local2global, a_m); 434 if (idex!=-1) 435 {v[idex] = 1.0;} 436 } 437 438 /* perform u = A.v_l */ 439 rvec_zero(u,n); 440 do_matvec(xxt_handle->mvi,v,u); 441 442 /* uu = X^T.u_l (local portion) */ 443 /* technically only need to zero out first i entries */ 444 /* later turn this into an XXT_solve call ? */ 445 rvec_zero(uu,m); 446 x_ptr=x; 447 iptr = col_indices; 448 for (k=0; k<i; k++) 449 { 450 off = *iptr++; 451 len = *iptr++; 452 453 uu[k] = BLASdot_(&len,u+off,&i1,x_ptr,&i1); 454 x_ptr+=len; 455 } 456 457 458 /* uu = X^T.u_l (comm portion) */ 459 ssgl_radd (uu, w, dim, stages); 460 461 /* z = X.uu */ 462 rvec_zero(z,n); 463 x_ptr=x; 464 iptr = col_indices; 465 for (k=0; k<i; k++) 466 { 467 off = *iptr++; 468 len = *iptr++; 469 470 BLASaxpy_(&len,&uu[k],x_ptr,&i1,z+off,&i1); 471 x_ptr+=len; 472 } 473 474 /* compute v_l = v_l - z */ 475 rvec_zero(v+a_n,a_m-a_n); 476 BLASaxpy_(&n,&dm1,z,&i1,v,&i1); 477 478 /* compute u_l = A.v_l */ 479 if (a_n!=a_m) 480 {gs_gop_hc(gs_handle,v,"+\0",dim);} 481 rvec_zero(u,n); 482 do_matvec(xxt_handle->mvi,v,u); 483 484 /* compute sqrt(alpha) = sqrt(v_l^T.u_l) - local portion */ 485 alpha = BLASdot_(&n,u,&i1,v,&i1); 486 /* compute sqrt(alpha) = sqrt(v_l^T.u_l) - comm portion */ 487 grop_hc(&alpha, &alpha_w, 1, op, dim); 488 489 alpha = (PetscScalar) sqrt((double)alpha); 490 491 /* check for small alpha */ 492 /* LATER use this to detect and determine null space */ 493 if (fabs(alpha)<1.0e-14) 494 {error_msg_fatal("bad alpha! %g\n",alpha);} 495 496 /* compute v_l = v_l/sqrt(alpha) */ 497 rvec_scale(v,1.0/alpha,n); 498 499 /* add newly generated column, v_l, to X */ 500 flag = 1; 501 off=len=0; 502 for (k=0; k<n; k++) 503 { 504 if (v[k]!=0.0) 505 { 506 len=k; 507 if (flag) 508 {off=k; flag=0;} 509 } 510 } 511 512 len -= (off-1); 513 514 if (len>0) 515 { 516 if ((xxt_nnz+len)>xxt_max_nnz) 517 { 518 error_msg_warning("increasing space for X by 2x!\n"); 519 xxt_max_nnz *= 2; 520 x_ptr = (PetscScalar *) malloc(xxt_max_nnz*sizeof(PetscScalar)); 521 rvec_copy(x_ptr,x,xxt_nnz); 522 free(x); 523 x = x_ptr; 524 x_ptr+=xxt_nnz; 525 } 526 xxt_nnz += len; 527 rvec_copy(x_ptr,v+off,len); 528 529 /* keep track of number of zeros */ 530 if (dim) 531 { 532 for (k=0; k<len; k++) 533 { 534 if (x_ptr[k]==0.0) 535 {xxt_zero_nnz++;} 536 } 537 } 538 else 539 { 540 for (k=0; k<len; k++) 541 { 542 if (x_ptr[k]==0.0) 543 {xxt_zero_nnz_0++;} 544 } 545 } 546 col_indices[2*i] = off; 547 col_sz[i] = col_indices[2*i+1] = len; 548 col_vals[i] = x_ptr; 549 } 550 else 551 { 552 col_indices[2*i] = 0; 553 col_sz[i] = col_indices[2*i+1] = 0; 554 col_vals[i] = x_ptr; 555 } 556 } 557 558 /* close off stages for execution phase */ 559 while (dim!=level) 560 { 561 stages[dim++]=i; 562 error_msg_warning("disconnected!!! dim(%d)!=level(%d)\n",dim,level); 563 } 564 stages[dim]=i; 565 566 xxt_handle->info->n=xxt_handle->mvi->n; 567 xxt_handle->info->m=m; 568 xxt_handle->info->nnz=xxt_nnz; 569 xxt_handle->info->max_nnz=xxt_max_nnz; 570 xxt_handle->info->msg_buf_sz=stages[level]-stages[0]; 571 xxt_handle->info->solve_uu = (PetscScalar *) malloc(m*sizeof(PetscScalar)); 572 xxt_handle->info->solve_w = (PetscScalar *) malloc(m*sizeof(PetscScalar)); 573 xxt_handle->info->x=x; 574 xxt_handle->info->col_vals=col_vals; 575 xxt_handle->info->col_sz=col_sz; 576 xxt_handle->info->col_indices=col_indices; 577 xxt_handle->info->stages=stages; 578 xxt_handle->info->nsolves=0; 579 xxt_handle->info->tot_solve_time=0.0; 580 581 free(segs); 582 free(u); 583 free(v); 584 free(uu); 585 free(z); 586 free(w); 587 588 return(0); 589 } 590 591 592 /*************************************xxt.c************************************ 593 Function: 594 595 Input : 596 Output: 597 Return: 598 Description: 599 **************************************xxt.c***********************************/ 600 static PetscErrorCode do_xxt_solve(xxt_ADT xxt_handle, PetscScalar *uc) 601 { 602 int off, len, *iptr; 603 int level =xxt_handle->level; 604 int n =xxt_handle->info->n; 605 int m =xxt_handle->info->m; 606 int *stages =xxt_handle->info->stages; 607 int *col_indices=xxt_handle->info->col_indices; 608 PetscScalar *x_ptr, *uu_ptr; 609 PetscScalar *solve_uu=xxt_handle->info->solve_uu; 610 PetscScalar *solve_w =xxt_handle->info->solve_w; 611 PetscScalar *x =xxt_handle->info->x; 612 PetscBLASInt i1 = 1; 613 614 PetscFunctionBegin; 615 uu_ptr=solve_uu; 616 rvec_zero(uu_ptr,m); 617 618 /* x = X.Y^T.b */ 619 /* uu = Y^T.b */ 620 for (x_ptr=x,iptr=col_indices; *iptr!=-1; x_ptr+=len) 621 { 622 off=*iptr++; len=*iptr++; 623 *uu_ptr++ = BLASdot_(&len,uc+off,&i1,x_ptr,&i1); 624 } 625 626 /* comunication of beta */ 627 uu_ptr=solve_uu; 628 if (level) {ssgl_radd(uu_ptr, solve_w, level, stages);} 629 630 rvec_zero(uc,n); 631 632 /* x = X.uu */ 633 for (x_ptr=x,iptr=col_indices; *iptr!=-1; x_ptr+=len) 634 { 635 off=*iptr++; len=*iptr++; 636 BLASaxpy_(&len,uu_ptr++,x_ptr,&i1,uc+off,&i1); 637 } 638 PetscFunctionReturn(0); 639 } 640 641 642 /*************************************Xxt.c************************************ 643 Function: check_init 644 645 Input : 646 Output: 647 Return: 648 Description: 649 **************************************xxt.c***********************************/ 650 static PetscErrorCode check_init(void) 651 { 652 PetscFunctionBegin; 653 comm_init(); 654 PetscFunctionReturn(0); 655 656 } 657 658 659 /*************************************xxt.c************************************ 660 Function: check_handle() 661 662 Input : 663 Output: 664 Return: 665 Description: 666 **************************************xxt.c***********************************/ 667 static PetscErrorCode check_handle(xxt_ADT xxt_handle) 668 { 669 int vals[2], work[2], op[] = {NON_UNIFORM,GL_MIN,GL_MAX}; 670 671 PetscFunctionBegin; 672 if (xxt_handle==NULL) 673 {error_msg_fatal("check_handle() :: bad handle :: NULL %d\n",xxt_handle);} 674 675 vals[0]=vals[1]=xxt_handle->id; 676 giop(vals,work,sizeof(op)/sizeof(op[0])-1,op); 677 if ((vals[0]!=vals[1])||(xxt_handle->id<=0)) 678 {error_msg_fatal("check_handle() :: bad handle :: id mismatch min/max %d/%d %d\n", 679 vals[0],vals[1], xxt_handle->id);} 680 PetscFunctionReturn(0); 681 } 682 683 684 /*************************************xxt.c************************************ 685 Function: det_separators 686 687 Input : 688 Output: 689 Return: 690 Description: 691 det_separators(xxt_handle, local2global, n, m, mylocmatvec, grid_data); 692 **************************************xxt.c***********************************/ 693 static PetscErrorCode det_separators(xxt_ADT xxt_handle) 694 { 695 int i, ct, id; 696 int mask, edge, *iptr; 697 int *dir, *used; 698 int sum[4], w[4]; 699 PetscScalar rsum[4], rw[4]; 700 int op[] = {GL_ADD,0}; 701 PetscScalar *lhs, *rhs; 702 int *nsep, *lnsep, *fo, nfo=0; 703 gs_ADT gs_handle=xxt_handle->mvi->gs_handle; 704 int *local2global=xxt_handle->mvi->local2global; 705 int n=xxt_handle->mvi->n; 706 int m=xxt_handle->mvi->m; 707 int level=xxt_handle->level; 708 int shared=FALSE; 709 710 PetscFunctionBegin; 711 dir = (int*)malloc(sizeof(PetscInt)*(level+1)); 712 nsep = (int*)malloc(sizeof(PetscInt)*(level+1)); 713 lnsep= (int*)malloc(sizeof(PetscInt)*(level+1)); 714 fo = (int*)malloc(sizeof(PetscInt)*(n+1)); 715 used = (int*)malloc(sizeof(PetscInt)*n); 716 717 ivec_zero(dir ,level+1); 718 ivec_zero(nsep ,level+1); 719 ivec_zero(lnsep,level+1); 720 ivec_set (fo ,-1,n+1); 721 ivec_zero(used,n); 722 723 lhs = (double*)malloc(sizeof(PetscScalar)*m); 724 rhs = (double*)malloc(sizeof(PetscScalar)*m); 725 726 /* determine the # of unique dof */ 727 rvec_zero(lhs,m); 728 rvec_set(lhs,1.0,n); 729 gs_gop_hc(gs_handle,lhs,"+\0",level); 730 rvec_zero(rsum,2); 731 for (ct=i=0;i<n;i++) 732 { 733 if (lhs[i]!=0.0) 734 {rsum[0]+=1.0/lhs[i]; rsum[1]+=lhs[i];} 735 } 736 grop_hc(rsum,rw,2,op,level); 737 rsum[0]+=0.1; 738 rsum[1]+=0.1; 739 /* if (!my_id) 740 { 741 printf("xxt n unique = %d (%g)\n",(int) rsum[0], rsum[0]); 742 printf("xxt n shared = %d (%g)\n",(int) rsum[1], rsum[1]); 743 }*/ 744 745 if (fabs(rsum[0]-rsum[1])>EPS) 746 {shared=TRUE;} 747 748 xxt_handle->info->n_global=xxt_handle->info->m_global=(int) rsum[0]; 749 xxt_handle->mvi->n_global =xxt_handle->mvi->m_global =(int) rsum[0]; 750 751 /* determine separator sets top down */ 752 if (shared) 753 { 754 for (iptr=fo+n,id=my_id,mask=num_nodes>>1,edge=level;edge>0;edge--,mask>>=1) 755 { 756 /* set rsh of hc, fire, and collect lhs responses */ 757 (id<mask) ? rvec_zero(lhs,m) : rvec_set(lhs,1.0,m); 758 gs_gop_hc(gs_handle,lhs,"+\0",edge); 759 760 /* set lsh of hc, fire, and collect rhs responses */ 761 (id<mask) ? rvec_set(rhs,1.0,m) : rvec_zero(rhs,m); 762 gs_gop_hc(gs_handle,rhs,"+\0",edge); 763 764 for (i=0;i<n;i++) 765 { 766 if (id< mask) 767 { 768 if (lhs[i]!=0.0) 769 {lhs[i]=1.0;} 770 } 771 if (id>=mask) 772 { 773 if (rhs[i]!=0.0) 774 {rhs[i]=1.0;} 775 } 776 } 777 778 if (id< mask) 779 {gs_gop_hc(gs_handle,lhs,"+\0",edge-1);} 780 else 781 {gs_gop_hc(gs_handle,rhs,"+\0",edge-1);} 782 783 /* count number of dofs I own that have signal and not in sep set */ 784 rvec_zero(rsum,4); 785 for (ivec_zero(sum,4),ct=i=0;i<n;i++) 786 { 787 if (!used[i]) 788 { 789 /* number of unmarked dofs on node */ 790 ct++; 791 /* number of dofs to be marked on lhs hc */ 792 if (id< mask) 793 { 794 if (lhs[i]!=0.0) 795 {sum[0]++; rsum[0]+=1.0/lhs[i];} 796 } 797 /* number of dofs to be marked on rhs hc */ 798 if (id>=mask) 799 { 800 if (rhs[i]!=0.0) 801 {sum[1]++; rsum[1]+=1.0/rhs[i];} 802 } 803 } 804 } 805 806 /* go for load balance - choose half with most unmarked dofs, bias LHS */ 807 (id<mask) ? (sum[2]=ct) : (sum[3]=ct); 808 (id<mask) ? (rsum[2]=ct) : (rsum[3]=ct); 809 giop_hc(sum,w,4,op,edge); 810 grop_hc(rsum,rw,4,op,edge); 811 rsum[0]+=0.1; rsum[1]+=0.1; rsum[2]+=0.1; rsum[3]+=0.1; 812 813 if (id<mask) 814 { 815 /* mark dofs I own that have signal and not in sep set */ 816 for (ct=i=0;i<n;i++) 817 { 818 if ((!used[i])&&(lhs[i]!=0.0)) 819 { 820 ct++; nfo++; 821 822 if (nfo>n) 823 {error_msg_fatal("nfo about to exceed n\n");} 824 825 *--iptr = local2global[i]; 826 used[i]=edge; 827 } 828 } 829 if (ct>1) {ivec_sort(iptr,ct);} 830 831 lnsep[edge]=ct; 832 nsep[edge]=(int) rsum[0]; 833 dir [edge]=LEFT; 834 } 835 836 if (id>=mask) 837 { 838 /* mark dofs I own that have signal and not in sep set */ 839 for (ct=i=0;i<n;i++) 840 { 841 if ((!used[i])&&(rhs[i]!=0.0)) 842 { 843 ct++; nfo++; 844 845 if (nfo>n) 846 {error_msg_fatal("nfo about to exceed n\n");} 847 848 *--iptr = local2global[i]; 849 used[i]=edge; 850 } 851 } 852 if (ct>1) {ivec_sort(iptr,ct);} 853 854 lnsep[edge]=ct; 855 nsep[edge]= (int) rsum[1]; 856 dir [edge]=RIGHT; 857 } 858 859 /* LATER or we can recur on these to order seps at this level */ 860 /* do we need full set of separators for this? */ 861 862 /* fold rhs hc into lower */ 863 if (id>=mask) 864 {id-=mask;} 865 } 866 } 867 else 868 { 869 for (iptr=fo+n,id=my_id,mask=num_nodes>>1,edge=level;edge>0;edge--,mask>>=1) 870 { 871 /* set rsh of hc, fire, and collect lhs responses */ 872 (id<mask) ? rvec_zero(lhs,m) : rvec_set(lhs,1.0,m); 873 gs_gop_hc(gs_handle,lhs,"+\0",edge); 874 875 /* set lsh of hc, fire, and collect rhs responses */ 876 (id<mask) ? rvec_set(rhs,1.0,m) : rvec_zero(rhs,m); 877 gs_gop_hc(gs_handle,rhs,"+\0",edge); 878 879 /* count number of dofs I own that have signal and not in sep set */ 880 for (ivec_zero(sum,4),ct=i=0;i<n;i++) 881 { 882 if (!used[i]) 883 { 884 /* number of unmarked dofs on node */ 885 ct++; 886 /* number of dofs to be marked on lhs hc */ 887 if ((id< mask)&&(lhs[i]!=0.0)) {sum[0]++;} 888 /* number of dofs to be marked on rhs hc */ 889 if ((id>=mask)&&(rhs[i]!=0.0)) {sum[1]++;} 890 } 891 } 892 893 /* go for load balance - choose half with most unmarked dofs, bias LHS */ 894 (id<mask) ? (sum[2]=ct) : (sum[3]=ct); 895 giop_hc(sum,w,4,op,edge); 896 897 /* lhs hc wins */ 898 if (sum[2]>=sum[3]) 899 { 900 if (id<mask) 901 { 902 /* mark dofs I own that have signal and not in sep set */ 903 for (ct=i=0;i<n;i++) 904 { 905 if ((!used[i])&&(lhs[i]!=0.0)) 906 { 907 ct++; nfo++; 908 *--iptr = local2global[i]; 909 used[i]=edge; 910 } 911 } 912 if (ct>1) {ivec_sort(iptr,ct);} 913 lnsep[edge]=ct; 914 } 915 nsep[edge]=sum[0]; 916 dir [edge]=LEFT; 917 } 918 /* rhs hc wins */ 919 else 920 { 921 if (id>=mask) 922 { 923 /* mark dofs I own that have signal and not in sep set */ 924 for (ct=i=0;i<n;i++) 925 { 926 if ((!used[i])&&(rhs[i]!=0.0)) 927 { 928 ct++; nfo++; 929 *--iptr = local2global[i]; 930 used[i]=edge; 931 } 932 } 933 if (ct>1) {ivec_sort(iptr,ct);} 934 lnsep[edge]=ct; 935 } 936 nsep[edge]=sum[1]; 937 dir [edge]=RIGHT; 938 } 939 /* LATER or we can recur on these to order seps at this level */ 940 /* do we need full set of separators for this? */ 941 942 /* fold rhs hc into lower */ 943 if (id>=mask) 944 {id-=mask;} 945 } 946 } 947 948 949 /* level 0 is on processor case - so mark the remainder */ 950 for (ct=i=0;i<n;i++) 951 { 952 if (!used[i]) 953 { 954 ct++; nfo++; 955 *--iptr = local2global[i]; 956 used[i]=edge; 957 } 958 } 959 if (ct>1) {ivec_sort(iptr,ct);} 960 lnsep[edge]=ct; 961 nsep [edge]=ct; 962 dir [edge]=LEFT; 963 964 xxt_handle->info->nsep=nsep; 965 xxt_handle->info->lnsep=lnsep; 966 xxt_handle->info->fo=fo; 967 xxt_handle->info->nfo=nfo; 968 969 free(dir); 970 free(lhs); 971 free(rhs); 972 free(used); 973 PetscFunctionReturn(0); 974 } 975 976 977 /*************************************xxt.c************************************ 978 Function: set_mvi 979 980 Input : 981 Output: 982 Return: 983 Description: 984 **************************************xxt.c***********************************/ 985 static 986 mv_info *set_mvi(int *local2global, int n, int m, void *matvec, void *grid_data) 987 { 988 mv_info *mvi; 989 990 991 mvi = (mv_info*)malloc(sizeof(mv_info)); 992 mvi->n=n; 993 mvi->m=m; 994 mvi->n_global=-1; 995 mvi->m_global=-1; 996 mvi->local2global=(int*)malloc((m+1)*sizeof(PetscInt)); 997 ivec_copy(mvi->local2global,local2global,m); 998 mvi->local2global[m] = INT_MAX; 999 mvi->matvec=(PetscErrorCode (*)(mv_info*,PetscScalar*,PetscScalar*))matvec; 1000 mvi->grid_data=grid_data; 1001 1002 /* set xxt communication handle to perform restricted matvec */ 1003 mvi->gs_handle = gs_init(local2global, m, num_nodes); 1004 1005 return(mvi); 1006 } 1007 1008 1009 /*************************************xxt.c************************************ 1010 Function: set_mvi 1011 1012 Input : 1013 Output: 1014 Return: 1015 Description: 1016 1017 computes u = A.v 1018 do_matvec(xxt_handle->mvi,v,u); 1019 **************************************xxt.c***********************************/ 1020 static PetscErrorCode do_matvec(mv_info *A, PetscScalar *v, PetscScalar *u) 1021 { 1022 PetscFunctionBegin; 1023 A->matvec((mv_info*)A->grid_data,v,u); 1024 PetscFunctionReturn(0); 1025 } 1026 1027 1028 1029