Speedup Sparse Symmetric Indefinite Matrix Solution

Hello,

i am trying to solve a general case least squares system:

N = ...
[ ...
    B*Q*B' , A , 0  ; 
      A'   , 0 , C' ;
      0    , C , 0  ;
]

with the right hand side

   rhs = [ -B*v0+f(x0,v0); 0 , -wc ].

N is sparse with nnz = 976328 and has 27016x27016 elements with the following pattern:

http://desmond.imageshack.us/Himg140/scaled.php?server=140&filename=sparse.png&res=landing

The three bands come from B*Q*B' with the size of 25464 x 25464. A is always very ill conditioned (rcond ~ 1-e17) therefore its not the usual Gauß-Markov solution:

dx = (A'*(B*Q*B')\A)\(A'*(B*Q*B')\(f(x0,v0)-B*v0);

where A will be on the main diagonal and destroy the whole N matrix condition.

After symamd the pattern shows a significant improvement:

http://desmond.imageshack.us/Himg845/scaled.php?server=845&filename=sparseamd.png&res=landing

The solution N\rhs takes usually 1-2min on my machine. In some cases it seems to end in an infinite loop. I kill the MATLAB process after 10mins.. of nothing.

1) I need some ideas how to solve it faster?

2) Will i have any benefit if i buy the parallel processing toolbox?

3) Do i need to change the code then?