7
$\begingroup$

Edit: I was advised to replace the question with a more specific one.

Coming from a very theoretical background, I'm pretty ignorant about what practical matrix solvers exist. (I have been, and will continue to scour the web for information, but I figured I would get direct and concise answers here as well.)

Currently, what are the most important matrix solvers? (implemented in any software)

I have a rudimentary programming background, and I'm familiar with classical theoretical methods for solving matrix systems. However, I'm well aware computer scientists have been at work finding ingenious ways to solve larger systems more quickly, especially for specialized classes of matrices.

I'm looking at applications of matrix solvers in industry, in particular for use in simulation programs.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hi rschwieb. Welcome to scicomp! This question is a bit too general for the StackExchange format. From the FAQ, you should only ask practical, answerable questions based on actual problems that you face. Chatty, open-ended questions diminish the usefulness of our site. $\endgroup$ – Aron Ahmadia Jun 7 '12 at 20:02
  • $\begingroup$ I'm going to close the question (to protect it from downvotes), which will allow you to edit it into something more specific you'd like to ask. For example, you've already let us know you're coming from a pure background. What level of studies are you entering? Any particular application area? Do you want recommendations for textbooks, examples of important research papers or software, something else? $\endgroup$ – Aron Ahmadia Jun 7 '12 at 20:03
  • $\begingroup$ Sorry that it is too general.. this is unfortunately a product of my ignorance of the topic. I'll try to make it less open ended. $\endgroup$ – rschwieb Jun 7 '12 at 20:08
  • $\begingroup$ @AronAhmadia I would like to enter industry on this topic, if that counts as studies :) I am able to understand Trefethen and Bau's text entirely, it's just I have no practical experience implementing such stuff in code. So, I'm unaware about what sort of software and methods exist outside of that text (it's mentioned in the answer below). $\endgroup$ – rschwieb Jun 7 '12 at 20:26
  • $\begingroup$ I'm not very good at mathematical English and sorry for being that boring, but doesn't "matrix solver" sound awkward?.. $\endgroup$ – faleichik Jun 8 '12 at 19:03
8
$\begingroup$

The best high-level overview that I know of is Trefethen and Bau. If I had to boil it down to a list, it would be (somewhat in pedagogical order):

  1. Dense $QR$ factorization
  2. Dense symmetric/Hermitian Eigenvalue Decomposition (EVD)
  3. Dense Singular Value Decomposition (SVD)
  4. The Conjugate Gradient Method (CG)
  5. Generalize Minimum Residual method (GMRES)
  6. Sparse Cholesky and $LU$ factorization
  7. "Fast" methods, such as multigrid, the Fast Fourier Transform (FFT), and the Fast Multipole Method (FMM)
|cite|improve this answer
$\endgroup$
  • $\begingroup$ :o By some strange luck, that is the only text on numerical linear algebra I own! Since my edition is from 1997 however, I'm a bit worried it's missing modern developments. I will certainly use this as a primer on the topic. Thank you for letting me know it is still useful! Please let me know if you think of any other famous method in use that do not appear in this text. $\endgroup$ – rschwieb Jun 7 '12 at 20:20
  • $\begingroup$ The main advancements have been in computing some of those decompositions faster, but the basic theory has not changed, IMO. I would also ensure at least passing familiarity with the Fast Fourier Transform (FFT) and Fast Multipole Methods (FMM), though the former is often only a component in a solver, and both are perhaps best thought of as fast matrix-vector multiplication for particular types of matrices. $\endgroup$ – Jack Poulson Jun 7 '12 at 20:28
  • $\begingroup$ Thank you, I will definitely take a long look at FFT and FMM. Someone has also alerted me that "the best known" methods are currently implemented in LAPACK, so I should familiarize myself with it. $\endgroup$ – rschwieb Jun 7 '12 at 21:02
  • $\begingroup$ I would agree that the recent algorithmic advances in serial dense EVD and SVD are almost all in LAPACK, but keep in mind that it is but a (large) part of an ecosystem. I am going to end the conversation there, because it is a long and detailed discussion that cannot be handled well in these comment boxes. $\endgroup$ – Jack Poulson Jun 7 '12 at 21:08
4
$\begingroup$

I second Jack Poulson's recommendation, but also want to recommend Yousef Saad's Iterative Methods for Sparse Linear Systems (available online, see here).

The main advantage of Saad is its discussion of the very important topic of preconditioning, something Trefethen and Bau does not touch. It also has pseudocode implementations of the standard algorithms, and talks about implementation details.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

From a practical viewpoint, and in addition to the texts referenced in the other answers, there's the book that everyone just calls the "Templates book". It has no theory, but it tells you a bit about how to implement iterative solvers.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.