2
$\begingroup$

This question is aimed at cleaning up an implementation detail of an in-house sparse direct solver. It uses METIS to reorder $A$ into $PAP^{T}$ for reduced fill-in. Inside the $Lx=b$ and $L^{T}x=b$ backsolution routines, the solver needs to apply the same permutation matrix to $b$ upon entry, then undo the permutation on $x$ just before returning. This is currently done with a temporary vector $t$, by copying $b$ with permutation into $t$, performing the $L$ and $L^{T}$ backsolves in-place on $t$, then copying $t$ with permutation back into $x$. (actually $b$ and $x$ are aliases for each other, but there's still the $t$-temporary)

I would like to redo this operation to be completely in-place, eliminating the temporary $t$. I think that in order do so, I need to take the permutation vector as computed by METIS and determine a sequence of row swaps that yields it. (Is this correct?) The algorithm that I was thinking to implement would basically be like a customized quicksort with a customized comparator. (The comparator would be customized so that it will correctly sort $\{0, 1, 2 ,3,\ldots,N\}$ into METIS's answer, the quicksort would be customized to record the atomic swap operations so that they can later be applied in-place to $b$).

My question is - is this the best way to accomplish what I am trying to do? I can tell already that the answer (a sequence of row swaps to realize $P$) is non-unique, because any sorting algorithm will yield an answer, but might perform completely different swaps. For example, bubblesort vs. quicksort will obviously yield different sequences - one with $O(n^2)$ swaps, the other with $O(n \log n)$, but both would work. I think finding the minimum number of swaps would be better for performance, hence the bias towards $O(n \log n)$ sort algorithms, but is there a different approach that would be guaranteed to find a minimum length sequence of swaps? I would think there would be some way to find a sequence that was $O(n)$ in length.

$\endgroup$
2
$\begingroup$

Can't you simply do it by swapping in the $i$th step the $i$th component with the component that contains the $i$th target component?

$\endgroup$
  • $\begingroup$ Maybe? The code is amalgamated multifrontal and its multithreaded internally, I am trying to avoid any swapping interleaved the numerics because its nonobvious to me what parts of the state vector are finished, which are active, and which are available for use as workspace at a given time. $\endgroup$ – rchilton1980 Jun 13 '12 at 16:32
  • $\begingroup$ This answer is correct.. think I missed the point on the first read. You can compute and store the O(n) swaps you need using this idea, then apply them to the rhs ahead of time, out of the actual numerics code. Thanks! $\endgroup$ – rchilton1980 Jun 13 '12 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.