5 ms·

explain matrix functions in more detail and how computing a matrix function on an upper triangular matrix is an advantage. how is this a fundamental tenet of n

by platz 3y ago

explain matrix functions in more detail and how computing a matrix function on an upper triangular matrix is an advantage. how is this a fundamental tenet of numerical linear algebra? also, if I just want the Eigendecomposition, why do I need schur decomposition? The motivation needs more explanation.

epgui 3y ago
Well, either it needs more explanation, or the audience is people with certain prerequisite knowledge.
cat_man 3y ago
Matrix functions (at least ones I learned about way back when) are Taylor series representations of a function with the matrix plugged in. For example: exp(A) = I + A + A^2/2 + ... + A^n/n! For matrices, you can show these end up as finite series (i.e., it can be written with the highest n being the dimension of the matrix) The A^n factors can be computed with fewer flops than dense matrices, I believe. The "Q's" don't involve little work since they're "unitary" and satisfy QQ = I, so that for example A^2 = (QTQ)^2 = (QTQQT) = QT^2Q* That's where the f(A)= Qf(T)Q* part comes from. It sounds to me like he's quoting what someone described as a "fundamental tenet of numerical linear algebra" as "anything Jordan decomposition can do, Schur can do better". He doesn't seem to be defending "this is a fundamental tenet", but is saying matrix functions illustrate the "Schur can do better" concept. Both Jordan decomposition and Schur are QTQ* decompositions, so I think he's justifying "Schur can do better" with his comments on poorer stability of Jordan form (i.e., the matrix function property depends on A = QTQ*, which both cases satisfy, but Schur has better numerical properties). I don't think the post said you need the Schur decomposition if you want an eigendecomposition (I'm taking to mean the full eigenvalue + eigenvector pair). It just pointed out that the diagonals are eigenvalues, the first column of Q will be have the eigenvector for the first eigenvalue, and you can obtain eigenvectors from the remaining info if you want it. I'm not sure what the typical approach is for doing eigendecompositions, it might not directly involve Schur decompositions at all. So I agree partially that you could add a little motivation to make it more self contained, but also agree it's probably aimed at a less general audience, like students who'd have more context around some stuff where the details are light.
- petters 3y ago
  > For matrices, you can show these end up as finite series (i.e., it can be written with the highest n being the dimension of the matrix) Can you clarify what you mean here? Don't we want the function to e.g. agree with the real-valued one for 1*1 matrices?
  - magicalhippo 3y ago
    From Wikipedia[1]: When X is an n×n diagonal matrix then exp(X) will be an n×n diagonal matrix with each diagonal element equal to the ordinary exponential applied to the corresponding diagonal element of X. Perhaps that's what GP meant? [1]: https://en.wikipedia.org/wiki/Matrix_exponential https://en.wikipedia.org/wiki/Matrix_exponential
  - cat_man 3y ago
    My memory is fuzzy on the details, but there's a way to show that if you have a series representation of a function that equals that converges to a=that function (i.e., an infinite sums of x^0, x^1, x^2, ..., x^n, ... with n going to infinity that equals f(x) - like the Taylor series of an exponential), that when you apply that to square matrices to represent a matrix function, there's an equivalent representation as a finite matrix polynomial. You can take the highest power of the equivalent finite polynomial as low as one less than the order of the matrix (so a matrix function of NxN matrix can be written as a N-1 degree matrix polynomial). In other words, for a square NxN matrix A and functions satisfying the appropriate conditions, this convergent infinite sum of increasing powers of A: c0 + c1A + c2A^2 + ... + cnA^n + ... can be written as the n-1 degree matrix polynomial: b0 + b1A + b2A^2 + .... + b_{n-1} A^(n-1) The coefficients b0, ..., b_{n-1} are different than the coefficients c0, c1, ... for the infinite series, but they evaluate to the same thing. Critical to the point you're making, the b0, b1, ..., b_{n-1} are different for differing choices of A, because the bn coefficients depend on the eigenvalues of the matrix. So you really have b0(A) + b1(A) * A, etc. The coefficients of the infinite series (c0, c1, ...) do not have this dependence on A. That makes the 1x1 case tautological, because b0(A) = f(A) That is, the finite series representation is the value of the function at its argument. There's some info on some of that here: https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem#Matrix_functions https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theore...
stabbles 3y ago
"why Schur vectors": stability + they're always computed when you compute eigenvectors. For non-symmetric matrices, the standard approach to compute an eigen decomposition is the QR algorithm, which is an iterative method that converges to a Schur decomposition AQ=QR. So, it's always cheaper to compute only Schur vectors. Eigenvectors are obtained by computing the eigen decomposition RY = YΛ (easy for R diagonal): A(QY) = (QY)Λ is the eigen decomposition of A. The QR algorithm works well because it uses stable operations throughout: householder reflections and given's rotations. Those preserve norm, so they don't amplify rounding errors. The Schur decomposition itself is useful for the same reason: Schur vectors are an orthonormal basis for eigenvectors. If you need to project something onto eigenvectors, it's more stable to work with Schur vectors than eigenvectors. The last step RY = YΛ is done implicitly, with a backwards solve involving R. If that matrix is badly conditioned, the eigenvectors have large errors.

by platz 3y ago

epgui 3y ago

Well, either it needs more explanation, or the audience is people with certain prerequisite knowledge.

cat_man 3y ago

Matrix functions (at least ones I learned about way back when) are Taylor series representations of a function with the matrix plugged in. For example: exp(A) = I + A + A^2/2 + ... + A^n/n! For matrices, you can show these end up as finite series (i.e., it can be written with the highest n being the dimension of the matrix) The A^n factors can be computed with fewer flops than dense matrices, I believe. The "Q's" don't involve little work since they're "unitary" and satisfy QQ = I, so that for example A^2 = (QTQ)^2 = (QTQQT) = QT^2Q* That's where the f(A)= Qf(T)Q* part comes from. It sounds to me like he's quoting what someone described as a "fundamental tenet of numerical linear algebra" as "anything Jordan decomposition can do, Schur can do better". He doesn't seem to be defending "this is a fundamental tenet", but is saying matrix functions illustrate the "Schur can do better" concept. Both Jordan decomposition and Schur are QTQ* decompositions, so I think he's justifying "Schur can do better" with his comments on poorer stability of Jordan form (i.e., the matrix function property depends on A = QTQ*, which both cases satisfy, but Schur has better numerical properties). I don't think the post said you need the Schur decomposition if you want an eigendecomposition (I'm taking to mean the full eigenvalue + eigenvector pair). It just pointed out that the diagonals are eigenvalues, the first column of Q will be have the eigenvector for the first eigenvalue, and you can obtain eigenvectors from the remaining info if you want it. I'm not sure what the typical approach is for doing eigendecompositions, it might not directly involve Schur decompositions at all. So I agree partially that you could add a little motivation to make it more self contained, but also agree it's probably aimed at a less general audience, like students who'd have more context around some stuff where the details are light.

petters 3y ago
> For matrices, you can show these end up as finite series (i.e., it can be written with the highest n being the dimension of the matrix) Can you clarify what you mean here? Don't we want the function to e.g. agree with the real-valued one for 1*1 matrices?
- magicalhippo 3y ago
  From Wikipedia[1]: When X is an n×n diagonal matrix then exp(X) will be an n×n diagonal matrix with each diagonal element equal to the ordinary exponential applied to the corresponding diagonal element of X. Perhaps that's what GP meant? [1]: https://en.wikipedia.org/wiki/Matrix_exponential https://en.wikipedia.org/wiki/Matrix_exponential
- cat_man 3y ago
  My memory is fuzzy on the details, but there's a way to show that if you have a series representation of a function that equals that converges to a=that function (i.e., an infinite sums of x^0, x^1, x^2, ..., x^n, ... with n going to infinity that equals f(x) - like the Taylor series of an exponential), that when you apply that to square matrices to represent a matrix function, there's an equivalent representation as a finite matrix polynomial. You can take the highest power of the equivalent finite polynomial as low as one less than the order of the matrix (so a matrix function of NxN matrix can be written as a N-1 degree matrix polynomial). In other words, for a square NxN matrix A and functions satisfying the appropriate conditions, this convergent infinite sum of increasing powers of A: c0 + c1A + c2A^2 + ... + cnA^n + ... can be written as the n-1 degree matrix polynomial: b0 + b1A + b2A^2 + .... + b_{n-1} A^(n-1) The coefficients b0, ..., b_{n-1} are different than the coefficients c0, c1, ... for the infinite series, but they evaluate to the same thing. Critical to the point you're making, the b0, b1, ..., b_{n-1} are different for differing choices of A, because the bn coefficients depend on the eigenvalues of the matrix. So you really have b0(A) + b1(A) * A, etc. The coefficients of the infinite series (c0, c1, ...) do not have this dependence on A. That makes the 1x1 case tautological, because b0(A) = f(A) That is, the finite series representation is the value of the function at its argument. There's some info on some of that here: https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem#Matrix_functions https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theore...

stabbles 3y ago

"why Schur vectors": stability + they're always computed when you compute eigenvectors. For non-symmetric matrices, the standard approach to compute an eigen decomposition is the QR algorithm, which is an iterative method that converges to a Schur decomposition AQ=QR. So, it's always cheaper to compute only Schur vectors. Eigenvectors are obtained by computing the eigen decomposition RY = YΛ (easy for R diagonal): A(QY) = (QY)Λ is the eigen decomposition of A. The QR algorithm works well because it uses stable operations throughout: householder reflections and given's rotations. Those preserve norm, so they don't amplify rounding errors. The Schur decomposition itself is useful for the same reason: Schur vectors are an orthonormal basis for eigenvectors. If you need to project something onto eigenvectors, it's more stable to work with Schur vectors than eigenvectors. The last step RY = YΛ is done implicitly, with a backwards solve involving R. If that matrix is badly conditioned, the eigenvectors have large errors.