1\par 2\subsection{Distributed Symbolic Factorization} 3\label{subsection:DChvMtx:symbolic-factorization} 4\par 5The symbolic factorization takes very little time when compared to the 6numeric factorization or a solve, but it can still be necessary to 7compute it in a distributed manner. 8For example, consider the case when the entries in the 9original matrix do not fit on one processor. 10\par 11Here is what we assume that can be present on one processor. 12\begin{enumerate} 13\item 14An {\tt ETree} front tree object 15contains five vectors whose length is the number of fronts 16(three tree vectors and two vectors to hold the number of internal 17and external vertices in a front) 18and one vector whose length is the number of vertices 19(that maps vertices to fronts). 20\item 21An {\tt IV} object that holds the map from a front to its owner. 22\item 23A {\tt DInpMtx} object that holds only those entries in the 24original matrix that will be mapped to fronts owned by the process. 25\end{enumerate} 26\par 27A process does not need to know about every front in the tree, 28only those that it owns, that it will update during the 29factorization, and those that it will interact with during the 30forward and backsolves. 31We {\it could} design a front tree data structure that holds 32only information about the fronts that a process needs to know about. 33However, it is quite likely that the overhead to store the entire 34front tree on each processor is acceptable. 35\par 36It is not so clear that we can afford to store the entire symbolic 37factorization on the front tree, so we have designed a strategy 38that each process computes and holds only the indices for the 39fronts that it needs. 40Actually, this is not true, for we store a bit more than the 41bare minimum, as we now explain. 42\par 43If a process owns front $J$, then it will compute the factor 44entries in this front, and will compute updates to all ancestor 45fronts $K$ such that $\bnd{J} \cap K \ne \emptyset$. 46Let the set of {\it active} fronts be the active fronts 47unioned with those fronts that will be updated by an owned front. 48% Let us call the set of {\it owned} fronts and those fronts that 49% will be updated by an owned front the {\it set of active fronts}. 50\par 51It is not necessarily true that an owned front $J$ will update 52{\it all} of its ancestors. 53However, to determine what ancestors of owned fronts will be updated 54by the owned fronts, we need to know the boundary indices for each 55front, and that is what we are trying to determine by computing the 56symbolic factorization. 57So we settle for a superset that is (hopefully) not too much larger 58than the active fronts. 59To use a different term, we will easily find a set of 60{\it supported fronts} that contains the active fronts. 61These supported fronts consists of the owned fronts and all 62ancestors of owned fronts, and we can determine this set just by 63using the front tree and the owners map vector. 64\par 65To compute the factorization, a process will need to have the 66indices for each of its active fronts, so at the end of the 67symbolic factorization, each process must contain an {\tt IVL} 68object that contains the front indices for all supported 69processors. 70\par 71How do we compute the front indices for the supported fronts? 72There are four steps. 73\begin{enumerate} 74\item 75From the front tree we know the number of internal and number of 76external indices in each front via the {\tt nodwghts[]} and {\tt 77bndwghts[]} vectors. 78So we initialize the {\tt IVL} object that will hold the supported 79portions of the symbolic factorization. 80\item 81For each owned front, we load the internal vertices using the 82{\tt vtxToFront[]} vector from the front tree. 83\item 84For each owned front $J$ we add some of the indices in $\bnd{J}$ by 85examining the entries in the local {\tt DInpMtx} object. 86\item 87Now we need to cooperate with the other processes. 88First we compute the number of messages that we expect to receive 89from other processes. 90There will be one message for each supported but unowned front, 91and one message for each unsupported front whose parent is owned. 92We keep track of the number of missing indices for each owned front. 93When all indices for an owned front are present (after step 2 94any root front has this property, and after step 3 all leaf fronts 95have this property), we put the front into a list of {\it ready} 96fronts. 97\begin{tabbing} 98XXX\=XXX\=XXX\=XXX\=XXX\=\kill 99\WHILE\ the ready list is not empty or there are messages remaining \\ 100\> \WHILE\ the ready list is not empty \\ 101\>\> remove owned front $J$ from the ready list \\ 102\>\> store $J \cup \bnd{J}$ in the {\tt IVL} object \\ 103\>\> send $J \cup \bnd{J}$ to all processes that contain $J$ in 104 their support sets \\ 105\>\> \IF\ the $J$ has a parent $K$ \THEN\ \\ 106\>\>\> \IF\ $K$ is owned and not complete \THEN\ \\ 107\>\>\>\> merge $\bnd{J}$ into $K \cup \bnd{K}$ \\ 108\>\>\>\> \IF\ $K \cup \bnd{K}$ is complete \THEN\ \\ 109\>\>\>\>\> put $K$ on the ready list \\ 110\>\>\>\> \END\ \IF \\ 111\>\>\> \ELSE\ \IF\ $J$ not supported by the owner of $K$ \THEN\ \\ 112\>\>\>\> send $J \cup \bnd{J}$ to the owner of $K$ \\ 113\>\>\> \END\ \IF \\ 114\>\> \END\ \IF\ \\ 115\> \END\ \WHILE\ \\ 116\> \WHILE\ there are messages waiting to be received \\ 117\>\> receive $J \cup \bnd{J}$ \\ 118\>\> \IF\ $J$ is supported \THEN\ \\ 119\>\>\> store $J \cup \bnd{J}$ in the {\tt IVL} object \\ 120\>\> \END\ \IF \\ 121\>\> \IF\ $J$ has a parent $K$, $K$ is owned and not complete \THEN\ \\ 122\>\>\> merge $\bnd{J}$ into $K \cup \bnd{K}$ \\ 123\>\>\> \IF\ $K \cup \bnd{K}$ is complete \THEN\ \\ 124\>\>\>\> put $K$ on the ready list \\ 125\>\>\> \END\ \IF \\ 126\>\> \END\ \IF \\ 127\> \END\ \WHILE \\ 128end \WHILE\ 129\end{tabbing} 130\end{enumerate} 131