Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The big six matrix factorizations

nhigham.com

Post reply on HN
Print view View original

11–20 of 84 posts

Re: The big six matrix factorizations

#11

Post by martinhath »

isaacfrond wrote: post #2

The article presents a note on the 6 well known matrix compositions. He states that all of them have cubic complexity, but practical algorithms with better exponents exist for all of them.

The fact that they're all cubic isn't really the notable part of the runtime of computing the different decompositions, because the constants involved are really different. In practice, a common reason for computing many of these decompositions is to solve a linear system `Ax=b`, because with the decomposition in hand it is really easy to solve the whole system (using e.g. backsubstitution). For instance, with C++s Eigen, look at the 100x100 column of [1], and we can see that there's orders of magnitude difference between the fast and slow approaches. THey're all still cubic, sure, but we're talking 168x difference here.

(of course, it's not so clear cut, since robustness varies, not all methods are applicable, and the benchmark is for solving the system, not computing the decomposition, but overall, knowledge of which decomposition is fast and which is not is absolutely crucial to practitioners)

[1]: https://eigen.tuxfamily.org/dox/group__DenseDecompositionBen...

Re: The big six matrix factorizations

#13

Post by hanche »

leephillips wrote: post #3

Thank you for this wonderfully concise summary: it’s convenient to have all this in one compact document. I suppose “flops” means “floating-point operations” here? Heretofore I’ve always encountered this as an abbreviation for “floating-point operations per second”.

Indeed, the meaning of “flops” is ambiguous, but that seems hard to avoid. Fortunately, the ambiguity is easily resolved from context in most cases, as it is here.

Re: The big six matrix factorizations

#14

Post by heinrichhartman »

From a theoretical perspective the most fundamental decomposition is the rank-decomposition:

A = X D Y

with X,Y invertible and D diagonal. It's called rank decomposition, because you can read off the rank from A by counting the non-zero entries in D. It's also useful to determining bases for the image and the kernel of A. Every math student learns a version of that in their first lecture series of Linear Algebra.

Curiously, the rank decomposition is not covered in the numerical literature. Also it's not possible to derive a rank decomposition from LR, QR decomposition, although the underlying algorithms (Gauss, Gram-Schmidt) could be used to do so.

It took me multiple weeks of work, to understand what the problem with this algorithms is, and what the practical options are to establish a rank decomposition are. Full details are available on my blog:

https://www.heinrichhartmann.com/posts/2021-03-08-rank-decom...

TL;DR. Your options are (1) SVD, (2) QR factorization with column pivoting (part of LAPACK), (3) LDU factorization with total pivoting (not implemented in BLAS/LAPACK/etc.)

Re: The big six matrix factorizations

#15

Post by nightski »

natly wrote: post #7
melling wrote: post #4

Any suggestions on what to learn in Linear Algebra after Gilbert Strang’s 18.06SC? https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011... My goal is to learn the math behind machine learning.

These lectures are fantastic after you've mastered the basics of linear algebra https://www.youtube.com/watch?v=McLq1hEq3UY (convex optimization, by a very experienced and often funny lecturer)

Stephen Boyd is a very good lecturer! I watched his videos on linear dynamical systems almost a decade ago and thought he did a fantastic job. Would highly recommend.

Re: The big six matrix factorizations

#16

Post by whatshisface »

heinrichhartman wrote: post #14

From a theoretical perspective the most fundamental decomposition is the rank-decomposition: A = X D Y with X,Y invertible and D diagonal. It's called rank decomposition, because you can read off the rank from A by counting the non-zero entries in D. It's also useful to determining bases for the image and the kernel of A. Every math student learns a version of that in their first lecture series of Linear Algebra. Cur…

What makes it the most fundamental?

Re: The big six matrix factorizations

#17

Post by edflsafoiewq »

whatshisface wrote: post #16
heinrichhartman wrote: post #14

From a theoretical perspective the most fundamental decomposition is the rank-decomposition: A = X D Y with X,Y invertible and D diagonal. It's called rank decomposition, because you can read off the rank from A by counting the non-zero entries in D. It's also useful to determining bases for the image and the kernel of A. Every math student learns a version of that in their first lecture series of Linear Algebra. Cur…

What makes it the most fundamental?

It's basically the matrix form of dim(domain(f)) = dim(ker(f)) + dim(im(f)), or domain(f)/ker(f) ≅ im(f) with f (inducing) the isomorphism.

Re: The big six matrix factorizations

#18

Post by heinrichhartman »

heinrichhartman wrote: post #14

From a theoretical perspective the most fundamental decomposition is the rank-decomposition: A = X D Y with X,Y invertible and D diagonal. It's called rank decomposition, because you can read off the rank from A by counting the non-zero entries in D. It's also useful to determining bases for the image and the kernel of A. Every math student learns a version of that in their first lecture series of Linear Algebra. Cur…

As it turns out, the author does cover the rank-decomposition (under the name "Rank-Revealing Factorization") in his blog as well:

https://nhigham.com/2021/05/19/what-is-a-rank-revealing-fact...

Re: The big six matrix factorizations

#19

Post by owlbite »

photon-torpedo wrote: post #9
isaacfrond wrote: post #2

The article presents a note on the 6 well known matrix compositions. He states that all of them have cubic complexity, but practical algorithms with better exponents exist for all of them.

> but practical algorithms with better exponents exist for all of them. I'm aware of randomized algorithms with better complexity, which come at the cost of only giving approximate results (though the approximation may be perfectly good for practical purposes). See e.g. [1]. Are there other approaches? [1] https://doi.org/10.1137/090771806

If the data is Sparse (which is not uncommon for large matrices in the real world), you can exploit the sparsity to do significantly better then O(n**3).
Post reply on HN