Mathematics desk
< October 4	<< Sep \| October \| Nov >>	October 6 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 5

Complexity of solving a sparse linear system

I am interested in estimating the asymptotic average run-time complexity of solving a sparse system of linear equations using typical iterative methods. Neither of these articles seem to provide a definitive answer. I assume the matrix A is n × n, with up to k arbitrarily positioned nonzero entries in every row and column, and we are looking for an approximate solution with tolerance ε. Thanks for any insight or references regarding the matter. 77.126.196.252 (talk) 13:54, 5 October 2008 (UTC)[reply]

Hi. Are you specifically not reducing the bandwidth? Once that is done the problem is much more deterministic. Saintrain (talk) 15:25, 5 October 2008 (UTC)[reply]

I haven't considered that. The article mentions bandwidth reduction for symmetric matrices, which mine isn't, but I do not see why symmetry is necessary. If applicable, I do not exclude bandwidth reduction, or any other robust preprocessing. What would the complexity look like in this case? Thanks. 77.126.196.252 (talk) 19:59, 5 October 2008 (UTC)[reply]

(Took me a while to remember back to the old days when things like this were important; modern PCs can handle "n"s of hundreds of thousands.) Not quite what you asked, and if I remember correctly (HA!), for a direct solution, the solution time will be about proportional to the sum of the A matrix column "heights" (up to the top-most non-zero element). Saintrain (talk) 23:31, 6 October 2008 (UTC)[reply]

(P.s. none of our business, but what is it?)

There is nothing stopping n from being in the millions for my application (which I choose not to disclose at this time). Things like this will probably always be important, since the more powerful computers become, the more will be expected of them. Thanks for the information. 87.70.182.250 (talk) 16:43, 9 October 2008 (UTC)[reply]