In my numerical linear algebra class we mentioned this problem briefly and according to some other lectures on the internet especially in data driven environments one mostly has to deal with such over- or underdetermined systems. Nevertheless in our lecture we mostly deal with direct methods (mostly matrix decompositions) and iterative methods (CG, GMRES, MINRES, ...) for different types of square! matrices.

Are there similar methods for under- or overdetermined systems?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Singular_value_decomposition $\endgroup$ Jul 3, 2022 at 17:46
  • 4
    $\begingroup$ Is the matrix in your system sparse or (nearly) all of the entries nonzero? Are you looking for a least squares solution in the overdetermined case or a minimum norm least squares solution in the underdetermined case? $\endgroup$ Jul 3, 2022 at 22:35
  • 1
    $\begingroup$ As you have seen, for square systems the answer changes significantly based on various features, and the same is true for rectangular systems. Sparse or dense? Which order of magnitude as for sizes? Both dimensions large or one much smaller? Underdetermined or overdetermined? $\endgroup$ Jul 4, 2022 at 6:47
  • $\begingroup$ @FedericoPoloni I don't actually have a problem which I have to solve, that's more like a general question because we didn't adress this problem in our class so I was just interested in how one proceeds for this kind of problem. I know that one way to do it is via the pseudoinverse which is for the most part just calculating the SVD. Do you maybe know some good material(papers, sites, literature,...) where one can read about these different factors when solving such a system(sparse and dense, magnitude of sizes, under- and overdetermined) $\endgroup$
    – Sen90
    Jul 4, 2022 at 12:53
  • 3
    $\begingroup$ OK I see, you are asking for a review of the problem, possibly with a "decision tree" for algorithms. Useful starting points are graduate books in numerical linear algebra such as the one by Trefethen-Bau, but there are many techniques around (from Krylov methods to randomized algorithms) and I am not sure I have the time and expertise for a full answer. $\endgroup$ Jul 4, 2022 at 16:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.