sparse linear system where A=I-beta*Q, Q sparse Markov transition matrix

[ben]

Hi everyone,

I need to solve a linear system Ax=b where A is a 1000x1000, 99% sparse matrix with the following particular structure: A=I - beta Q, where beta<1 but close to 1 (eg 0.995) and Q is a sparse Markov transition matrix (all coefficients 0<q<1, rows sum to one). What would be a good way to approach this? I have tried direct factorization methods as well as the various lsqr() methods available in Julia packages, treating A as any other sparse matrix, but was not successful. Do you know of any method that would leverage the particular structure of A? Alternatively, what might be good options to try with methods such as lsqr(), for instance what type of preconditoning, etc.?

Thank you.

Ben

[Christoph Ortner]

How can a sparse direct solver fail? That seems strange to me. With 1000 x 1000  even a full direct solver should take no time:

julia> A = rand(1000,1000); b = rand(1000); @time A \ b;

  0.023178 seconds (15 allocations: 7.645 MB)

[ben]

Hi, thanks for taking the time to reply. You made me go back and find a reference/copy error deep in my code... because of badly designed tests and bad luck in the circumstances triggering an error I had managed to convince myself the issue came from this linear system. Thanks again. Ben