SortedList_dh.c

00001 /*@HEADER
00002 // ***********************************************************************
00003 //
00004 //       Ifpack: Object-Oriented Algebraic Preconditioner Package
00005 //                 Copyright (2009) Sandia Corporation
00006 //
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 //
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00025 //
00026 // ***********************************************************************
00027 //@HEADER
00028 */
00029 
00030 #include "SortedList_dh.h"
00031 #include "Mem_dh.h"
00032 #include "Parser_dh.h"
00033 #include "Hash_i_dh.h"
00034 #include "SubdomainGraph_dh.h"
00035 
00036 
00037 struct _sortedList_dh
00038 {
00039   int m;            /* number of local rows */
00040   int row;          /* local number of row being factored */
00041   int beg_row;          /* global number of first locally owned row, wrt A */
00042   int beg_rowP;         /* global number of first locally owned row, wrt F */
00043   int count;            /* number of items entered in the list, 
00044                    plus 1 (for header node) 
00045                  */
00046   int countMax;         /* same as count, but includes number of items that my have
00047                    been deleted from calling SortedList_dhEnforceConstraint()
00048                  */
00049   int *o2n_local;       /* not owned! */
00050   Hash_i_dh o2n_external;   /* not owned! */
00051 
00052   SRecord *list;        /* the sorted list */
00053   int alloc;            /* allocated length of list */
00054   int getLower;         /* index used for returning lower tri elts */
00055   int get;          /* index of returning all elts; */
00056 
00057   bool debug;
00058 };
00059 
00060 static void lengthen_list_private (SortedList_dh sList);
00061 
00062 
00063 #undef __FUNC__
00064 #define __FUNC__ "SortedList_dhCreate"
00065 void
00066 SortedList_dhCreate (SortedList_dh * sList)
00067 {
00068   START_FUNC_DH
00069     struct _sortedList_dh *tmp =
00070     (struct _sortedList_dh *) MALLOC_DH (sizeof (struct _sortedList_dh));
00071   CHECK_V_ERROR;
00072   *sList = tmp;
00073   tmp->m = 0;
00074   tmp->row = -1;
00075   tmp->beg_row = 0;
00076   tmp->count = 1;
00077   tmp->countMax = 1;
00078   tmp->o2n_external = NULL;
00079   tmp->o2n_local = NULL;
00080 
00081   tmp->get = 0;
00082   tmp->getLower = 0;
00083   tmp->alloc = 0;
00084   tmp->list = NULL;
00085   tmp->debug = Parser_dhHasSwitch (parser_dh, "-debug_SortedList");
00086 END_FUNC_DH}
00087 
00088 
00089 #undef __FUNC__
00090 #define __FUNC__ "SortedList_dhDestroy"
00091 void
00092 SortedList_dhDestroy (SortedList_dh sList)
00093 {
00094   START_FUNC_DH if (sList->list != NULL)
00095     {
00096       FREE_DH (sList->list);
00097       CHECK_V_ERROR;
00098     }
00099   FREE_DH (sList);
00100   CHECK_V_ERROR;
00101 END_FUNC_DH}
00102 
00103 
00104 #undef __FUNC__
00105 #define __FUNC__ "SortedList_dhInit"
00106 void
00107 SortedList_dhInit (SortedList_dh sList, SubdomainGraph_dh sg)
00108 {
00109   START_FUNC_DH sList->o2n_local = sg->o2n_col;
00110   sList->m = sg->m;
00111   sList->beg_row = sg->beg_row[myid_dh];
00112   sList->beg_rowP = sg->beg_rowP[myid_dh];
00113   sList->count = 1;     /* "1" is for the header node */
00114   sList->countMax = 1;      /* "1" is for the header node */
00115   sList->o2n_external = sg->o2n_ext;
00116 
00117   /* heuristic: "m" should be a good number of nodes */
00118   sList->alloc = sList->m + 5;
00119   sList->list = (SRecord *) MALLOC_DH (sList->alloc * sizeof (SRecord));
00120   sList->list[0].col = INT_MAX;
00121   sList->list[0].next = 0;
00122 END_FUNC_DH}
00123 
00124 
00125 #undef __FUNC__
00126 #define __FUNC__ "SortedList_dhReset"
00127 void
00128 SortedList_dhReset (SortedList_dh sList, int row)
00129 {
00130   START_FUNC_DH sList->row = row;
00131   sList->count = 1;
00132   sList->countMax = 1;
00133   sList->get = 0;
00134   sList->getLower = 0;
00135   sList->list[0].next = 0;
00136 END_FUNC_DH}
00137 
00138 
00139 #undef __FUNC__
00140 #define __FUNC__ "SortedList_dhReadCount"
00141 int
00142 SortedList_dhReadCount (SortedList_dh sList)
00143 {
00144 START_FUNC_DH END_FUNC_VAL (sList->count - 1)}
00145 
00146 #undef __FUNC__
00147 #define __FUNC__ "SortedList_dhResetGetSmallest"
00148 void
00149 SortedList_dhResetGetSmallest (SortedList_dh sList)
00150 {
00151   START_FUNC_DH sList->getLower = 0;
00152   sList->get = 0;
00153 END_FUNC_DH}
00154 
00155 #undef __FUNC__
00156 #define __FUNC__ "SortedList_dhGetSmallest"
00157 SRecord *
00158 SortedList_dhGetSmallest (SortedList_dh sList)
00159 {
00160   START_FUNC_DH SRecord * node = NULL;
00161   SRecord *list = sList->list;
00162   int get = sList->get;
00163 
00164   get = list[get].next;
00165 
00166   if (list[get].col < INT_MAX)
00167     {
00168       node = &(list[get]);
00169       sList->get = get;
00170     }
00171 END_FUNC_VAL (node)}
00172 
00173 #undef __FUNC__
00174 #define __FUNC__ "SortedList_dhGetSmallestLowerTri"
00175 SRecord *
00176 SortedList_dhGetSmallestLowerTri (SortedList_dh sList)
00177 {
00178   START_FUNC_DH SRecord * node = NULL;
00179   SRecord *list = sList->list;
00180   int getLower = sList->getLower;
00181   int globalRow = sList->row + sList->beg_rowP;
00182 
00183   getLower = list[getLower].next;
00184 
00185   if (list[getLower].col < globalRow)
00186     {
00187       node = &(list[getLower]);
00188       sList->getLower = getLower;
00189     }
00190 END_FUNC_VAL (node)}
00191 
00192 
00193 #undef __FUNC__
00194 #define __FUNC__ "SortedList_dhPermuteAndInsert"
00195 bool
00196 SortedList_dhPermuteAndInsert (SortedList_dh sList, SRecord * sr,
00197                    double thresh)
00198 {
00199   START_FUNC_DH bool wasInserted = false;
00200   int col = sr->col;
00201   double testVal = fabs (sr->val);
00202   int beg_row = sList->beg_row, end_row = beg_row + sList->m;
00203   int beg_rowP = sList->beg_rowP;
00204 
00205   /* insertion of local indices */
00206   if (col >= beg_row && col < end_row)
00207     {
00208       /* convert to local indexing  and permute */
00209       col -= beg_row;
00210       col = sList->o2n_local[col];
00211 
00212       /* sparsification */
00213       if (testVal > thresh || col == sList->row)
00214     {
00215       col += beg_rowP;
00216     }
00217       else
00218     {
00219       col = -1;
00220 /*
00221 fprintf(logFile, "local row: %i  DROPPED: col= %i  val= %g (thresh= %g)\n",
00222                            sList->row+1, sr->col+1, testVal, thresh);
00223 */
00224     }
00225     }
00226 
00227 
00228   /* insertion of external indices */
00229   else
00230     {
00231       /* sparsification for external indices */
00232       if (testVal < thresh)
00233     goto END_OF_FUNCTION;
00234 
00235       /* permute column index */
00236       if (sList->o2n_external == NULL)
00237     {
00238       col = -1;
00239     }
00240       else
00241     {
00242       int tmp = Hash_i_dhLookup (sList->o2n_external, col);
00243       CHECK_ERROR (-1);
00244       if (tmp == -1)
00245         {
00246           col = -1;
00247         }
00248       else
00249         {
00250           col = tmp;
00251         }
00252     }
00253     }
00254 
00255   if (col != -1)
00256     {
00257       sr->col = col;
00258       SortedList_dhInsert (sList, sr);
00259       CHECK_ERROR (-1);
00260       wasInserted = true;
00261     }
00262 
00263 END_OF_FUNCTION:;
00264 
00265 END_FUNC_VAL (wasInserted)}
00266 
00267 
00268 #undef __FUNC__
00269 #define __FUNC__ "SortedList_dhInsertOrUpdate"
00270 void
00271 SortedList_dhInsertOrUpdate (SortedList_dh sList, SRecord * sr)
00272 {
00273   START_FUNC_DH SRecord * node = SortedList_dhFind (sList, sr);
00274   CHECK_V_ERROR;
00275 
00276   if (node == NULL)
00277     {
00278       SortedList_dhInsert (sList, sr);
00279       CHECK_V_ERROR;
00280     }
00281   else
00282     {
00283       node->level = MIN (sr->level, node->level);
00284     }
00285 END_FUNC_DH}
00286 
00287 
00288 /* note: this does NOT check to see if item was already inserted! */
00289 #undef __FUNC__
00290 #define __FUNC__ "SortedList_dhInsert"
00291 void
00292 SortedList_dhInsert (SortedList_dh sList, SRecord * sr)
00293 {
00294   START_FUNC_DH int prev, next;
00295   int ct, col = sr->col;
00296   SRecord *list = sList->list;
00297 
00298   /* lengthen list if out of space */
00299   if (sList->countMax == sList->alloc)
00300     {
00301       lengthen_list_private (sList);
00302       CHECK_V_ERROR;
00303       list = sList->list;
00304     }
00305 
00306   /* add new node to end of list */
00307   ct = sList->countMax;
00308   sList->countMax += 1;
00309   sList->count += 1;
00310 
00311   list[ct].col = col;
00312   list[ct].level = sr->level;
00313   list[ct].val = sr->val;
00314 
00315   /* splice new node into list */
00316   prev = 0;
00317   next = list[0].next;
00318   while (col > list[next].col)
00319     {
00320       prev = next;
00321       next = list[next].next;
00322     }
00323   list[prev].next = ct;
00324   list[ct].next = next;
00325 END_FUNC_DH}
00326 
00327 
00328 #undef __FUNC__
00329 #define __FUNC__ "SortedList_dhFind"
00330 SRecord *
00331 SortedList_dhFind (SortedList_dh sList, SRecord * sr)
00332 {
00333   START_FUNC_DH int i, count = sList->countMax;
00334   int c = sr->col;
00335   SRecord *s = sList->list;
00336   SRecord *node = NULL;
00337 
00338   /* no need to traverse list in sorted order */
00339   for (i = 1; i < count; ++i)
00340     {               /* start at i=1, since i=0 would be header node */
00341 
00342       if (s[i].col == c)
00343     {
00344       node = &(s[i]);
00345       break;
00346     }
00347     }
00348 
00349 END_FUNC_VAL (node)}
00350 
00351 #undef __FUNC__
00352 #define __FUNC__ "lengthen_list_private"
00353 void
00354 lengthen_list_private (SortedList_dh sList)
00355 {
00356   START_FUNC_DH SRecord * tmp = sList->list;
00357   int size = sList->alloc = 2 * sList->alloc;
00358 
00359   SET_INFO ("lengthening list");
00360 
00361   sList->list = (SRecord *) MALLOC_DH (size * sizeof (SRecord));
00362   memcpy (sList->list, tmp, sList->countMax * sizeof (SRecord));
00363   SET_INFO ("doubling size of sList->list");
00364   FREE_DH (tmp);
00365   CHECK_V_ERROR;
00366 END_FUNC_DH}
00367 
00368 
00369 /*=====================================================================
00370  * functions for enforcing subdomain constraint 
00371  *=====================================================================*/
00372 
00373 
00374 static bool check_constraint_private (SubdomainGraph_dh sg,
00375                       int thisSubdomain, int col);
00376 void delete_private (SortedList_dh sList, int col);
00377 
00378 #undef __FUNC__
00379 #define __FUNC__ "SortedList_dhEnforceConstraint"
00380 void
00381 SortedList_dhEnforceConstraint (SortedList_dh sList, SubdomainGraph_dh sg)
00382 {
00383   START_FUNC_DH int thisSubdomain = myid_dh;
00384   int col, count;
00385   int beg_rowP = sList->beg_rowP;
00386   int end_rowP = beg_rowP + sList->m;
00387   bool debug = false;
00388 
00389   if (Parser_dhHasSwitch (parser_dh, "-debug_SortedList"))
00390     debug = true;
00391 
00392   if (debug)
00393     {
00394       fprintf (logFile, "SLIST ======= enforcing constraint for row= %i\n",
00395            1 + sList->row);
00396 
00397       fprintf (logFile, "\nSLIST ---- before checking: ");
00398       count = SortedList_dhReadCount (sList);
00399       CHECK_V_ERROR;
00400       while (count--)
00401     {
00402       SRecord *sr = SortedList_dhGetSmallest (sList);
00403       CHECK_V_ERROR;
00404       fprintf (logFile, "%i ", sr->col + 1);
00405     }
00406       fprintf (logFile, "\n");
00407       sList->get = 0;
00408     }
00409 
00410   /* for each column index in the list */
00411   count = SortedList_dhReadCount (sList);
00412   CHECK_V_ERROR;
00413 
00414   while (count--)
00415     {
00416       SRecord *sr = SortedList_dhGetSmallest (sList);
00417       CHECK_V_ERROR;
00418       col = sr->col;
00419 
00420       if (debug)
00421     {
00422       fprintf (logFile, "SLIST  next col= %i\n", col + 1);
00423     }
00424 
00425 
00426       /* if corresponding row is nonlocal */
00427       if (col < beg_rowP || col >= end_rowP)
00428     {
00429 
00430       if (debug)
00431         {
00432           fprintf (logFile, "SLIST     external col: %i ; ", 1 + col);
00433         }
00434 
00435       /* if entry would violate subdomain constraint, discard it
00436          (snip it out of the list)
00437        */
00438       if (check_constraint_private (sg, thisSubdomain, col))
00439         {
00440           delete_private (sList, col);
00441           CHECK_V_ERROR;
00442           sList->count -= 1;
00443 
00444           if (debug)
00445         {
00446           fprintf (logFile, " deleted\n");
00447         }
00448         }
00449       else
00450         {
00451           if (debug)
00452         {
00453           fprintf (logFile, " kept\n");
00454         }
00455         }
00456     }
00457     }
00458   sList->get = 0;
00459 
00460   if (debug)
00461     {
00462       fprintf (logFile, "SLIST---- after checking: ");
00463       count = SortedList_dhReadCount (sList);
00464       CHECK_V_ERROR;
00465       while (count--)
00466     {
00467       SRecord *sr = SortedList_dhGetSmallest (sList);
00468       CHECK_V_ERROR;
00469       fprintf (logFile, "%i ", sr->col + 1);
00470     }
00471       fprintf (logFile, "\n");
00472       fflush (logFile);
00473       sList->get = 0;
00474     }
00475 
00476 END_FUNC_DH}
00477 
00478 
00479 /* this is similar to a function in ilu_seq.c */
00480 #undef __FUNC__
00481 #define __FUNC__ "check_constraint_private"
00482 bool
00483 check_constraint_private (SubdomainGraph_dh sg, int p1, int j)
00484 {
00485   START_FUNC_DH bool retval = false;
00486   int i, p2;
00487   int *nabors, count;
00488 
00489   p2 = SubdomainGraph_dhFindOwner (sg, j, true);
00490 
00491   nabors = sg->adj + sg->ptrs[p1];
00492   count = sg->ptrs[p1 + 1] - sg->ptrs[p1];
00493 
00494   for (i = 0; i < count; ++i)
00495     {
00496       if (nabors[i] == p2)
00497     {
00498       retval = true;
00499       break;
00500     }
00501     }
00502 
00503 END_FUNC_VAL (!retval)}
00504 
00505 #undef __FUNC__
00506 #define __FUNC__ "delete_private"
00507 void
00508 delete_private (SortedList_dh sList, int col)
00509 {
00510   START_FUNC_DH int curNode = 0;
00511   SRecord *list = sList->list;
00512   int next;
00513 
00514   /* find node preceeding the node to be snipped out */
00515   /* 'list[curNode].next' is array index of the next node in the list */
00516 
00517   while (list[list[curNode].next].col != col)
00518     {
00519       curNode = list[curNode].next;
00520     }
00521 
00522   /* mark node to be deleted as inactive (needed for Find()) */
00523   next = list[curNode].next;
00524   list[next].col = -1;
00525 
00526   /* snip */
00527   next = list[next].next;
00528   list[curNode].next = next;
00529 END_FUNC_DH}

Generated on Wed May 12 21:30:18 2010 for IFPACK by  doxygen 1.4.7