Question

Is there an algorithm (computer science) that can solve large system of equations like (100 variables, 100 equations) quickly and efficiently on a reasonably good computer? I have this doubt as I am implementing a algorithm that solve large system of equations to find local and global extremas.

Answer 1

I have a system of NN linear equations, Ax=bAx=b, in NN unknowns (where NN is large).

If I am interested in the solution for only one of the unknowns, what are the best approaches?

For example, assume N=50,000N=50,000. We want the solution for x1x1 through x100x100 only. Is there any trick that does not require O(n3)O(n3) (or OO(matrix inversion))
PLZ PLZ mark me BRAINLIEST

Answer 2

HEY MATE HOPE IT WILL HELP YOU
For symmetric positive matrices:

Cholesky

CG

MINRES, MINRES-QLP are attractive for symmetric and indefinite matrices.

For sparse matrices look at these:

Golub, van Loan: Matrix Computations (still the classical reference on matrix algorithms; does not explicitly treat sparse matrices; a bit terse)

Davis: Direct Methods for Sparse Linear Systems (a good introduction on decomposition methods for sparse matrices)

Duff: Direct Methods (review paper; more details on modern "multifrontal" direct methods for sparse matrices)

Saad: Iterative methods for sparse linear systems (the theory and - to a lesser extent - practice of Krylov methods)

The Section 4 /decision tree/ of the relevant chapter in the NAG Library Manual also answers some of your questions.

Friedrich-Alexander-University of Erlangen-Nürnberg

CG is actually a method for symmetric positive definite matrices.

Moreover, 10^6 is not that big of a matrix - at least in scientific computing.

When stored in CRS format and double precision, it shouldn't take more than 108 MBytes of memory. CG, GMRES and similary methods can easily handle systems of that size if implemented correctly in a decent way.

Could you give a few more details on your application and how often you must invert the matrix? Is your matrix positive definite or just symmetric?

Your sparsity structure looks similar to what you get from stencil codes or finite element methods. Hence, if your matrix doesn't change but is applied multiple times, it might be efficient to use a direct method (e.g., LDLT). For that you could have a look at the MUMPS library.