1

I've got a linear equation $A_{n*n}\cdot x=1_n$, where $n=1000000$ and $A$ is symmetric with approx $1000$ nonzero entries in each column and row. What would be the best numerically stable algorithm to handle linear equations of that size?

Michael
  • 1,649
  • 10
  • 16
  • What software can you use? If you can write a MATLAB code, you save $A$ as a sparse matrix format (which mainly does not save zeroes), and you can just write the backslash operator. Thus, $A=x$ \ $ones(n,1)$ will use the most efficient algorithm for solving the system. I guess it will use Gauss-Jordan method, but I'm not sure. – 7raiden7 May 09 '14 at 09:35
  • @7raiden7: I have to implement this in C++. The question is not about soft though, it's about choosing an algorithms. Inverting $A$ would be infeasible. $SVD$ or $LU$ decomposition? I don't know whether the triangular matrices would become dense. If so than decompositions would also be infeasible. Iterative? Depends how much precision I would loose on a matrix of that size... – Michael May 09 '14 at 16:07
  • If you use a Gauss-Seidel approach you can monitor the error, namely $e_n=x_{n+1}-x_n$. But still, you have to make sure that you verify the convergence hypothesis for the algorithm. But it can worth a try. – 7raiden7 May 11 '14 at 11:26

0 Answers0