Georgia Tech! Anyone else just finish taking Graduate Algorithms? Hope you passed.
Hah! I took that course with Vijay Vazirani almost a decade ago.
Interactive Linear Algebra (2019)
41–43 of 43 posts
Re: Interactive Linear Algebra (2019)
#42Earlier quoted context omitted.
I only consider positive semi-definite symmetric matrices. A = D * R is almost certainly not such a matrix. The positive semi-definite symmetric case is the only one needed to compute SVDs. A proof of convergence for the algorithm is only known for certain families of matrices. These include the positive-definite symmetric matrices, all symmetric matrices (once suitable improvements to the algorithm are made), the He…
Ah, okay. Sure. And PSD matrix A is diagonalizeable with orthogonal matrices i.e. A = Q^T * D * Q The ellipsoid visualization you meant is insensitive to the Q term (any rotation of a sphere is the same sphere), but not to the Q^T term. What I am still failing to understand is this sentence from the article: > The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix. It sou…
>> Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A.
> So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix?
Yes. Each iteration of QR (and LR) turns a PSD matrix into another PSD matrix. A PSD matrix in Schur form is necessarily a diagonal matrix.
>> The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix.
> It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned?
My visualization technique assumes that the matrix is PSD. In the PSD case, there is a one-to-one correspondence between ellipsoids and PSD matrices. I don't know what happens if you apply it to non-PSD matrices, but the one-to-one correspondence gets lost.
Re: Interactive Linear Algebra (2019)
#43I've only just skimmed through this. And it's a subject I already know so I can't tell if it's actually a good resource. However, my initial impression is that I love it. I think that textbooks, math textbooks in particular, are an example where print publishing does a disservice. (I'm counting PDFs here too.) By having to lay everything out in print form, you have to clutter up your explanations with examples and fo…
> I think that textbooks, math textbooks in particular, are an example where print publishing does a disservice. (I'm counting PDFs here too.) By having to lay everything out in print form, you have to clutter up your explanations with examples and footnotes that take up physical room. Here, the examples are toggle-able. If I _want_ to explore an example, I can. But I don't need to. This kind of thing is especially h…
I had never seen Lamport's idea of structured proofs. I just read the linked paper and I love it.