pages tagged sparse matrixJason's Chatterhttp://lovesgoodfood.com/jason/tags/sparse_matrix/Jason's Chatterikiwiki2011-04-19T18:44:59ZJust to put a stake in the groundhttp://lovesgoodfood.com/jason/posts/Just_to_put_a_stake_in_the_ground/2011-04-19T18:44:59Z2011-04-19T18:44:59Z
<p>I keep forgetting to write this up, but it’s related to static pivoting for symmetric indefinite problems. Existing work forms a weighted matching on the log of a matrix’s elements as in <a href="http://etna.mcs.kent.edu/vol.23.2006/pp158-179.dir/pp158-179.html">Schenk and Gärtner, 2006</a> and <a href="http://en.scientificcommons.org/980523">Duff and Pralett, 2005</a>.</p>
<p>Both report limited success, but they’re using the wrong weights and making the problem far too complicated.</p>
<p>Don’t use the matrix’s elements, use the potential <strong>pivots</strong>. In the symmetric indefinite case, that means replacing the off-diagonal elements by the 2x2 determinant of the respective submatrix. Element <em>A(i, j)</em> with <em>i ≠ j</em> is replaced by abs (det ([<em>A(i,i)</em>, <em>A(i,j)</em>; <em>A(j,i)</em>, <em>A(j,j)</em>])). Element <em>A(i,i)</em> is replaced by abs (<em>A(i,i)</em>) and is treated as a self-loop. If a maximum-weight matching pairs <em>i</em> with itself, use a 1x1 pivot. Otherwise use the respective 2x2 pivot. No need to find cycles, break loops, <i>etc</i>.</p>
<p>I haven’t tested the idea thoroughly, but I can’t see how it possibly could be worse than the more contrived contraptions. This feels like the natural analog, and also could map perturbations of small pivots directly to original entries.</p>