0
$\begingroup$

I have a matrix in the form of $2n\times 2n$ block matrix

$$ A = \begin{pmatrix}O& W\\ J& D\end{pmatrix} $$

where, $O$ is an $n\times n$ zero-matrix; $W$ is a n-by-n diagonal matrix, $W = w_0I$, where $w_0$ is a constant scalar, $I$ is an n-by-n identity matrix; J is an n-by-n full matrix almost symmetric; D is an n-by-n diagonal matrix with different diagonal elements.

Due to some needs, I have to compute all the eigenvalues of A.

(Note: I don't care about eigenvectors)

And by some manipulation that is omitted here), I finally found that, the eigenvalue of A can be calculated based on a intermediate results of its sub-matrix: J.

My claim is that, typically, the complexity of eigenvalue problem is O(n^3) for calculation directly on A, so when the matrix size become half, the complexity reduced roughly to 1/8*O(n^3) for calculation directly on J (overlook some overhead computational time).

The computational time in MATLAB (eig() command) supports my idea, that, by my approach, the overall computational time is reduced.

However, one of my colleagues challenged me , said: "For large systems, a dense matrix, even if smaller than the actual state matrix, can lead to numerical problems. It is preferable a larger but sparse matrix. "

Well, I have doubt on his comments/critics on my special case.

Yes, it is true that matrix A is "relatively" sparse, but the sparse pattern is not as usual as we often see in a symmetric, sparse matrix. Note that, here , both A and J are non-symmetric. (Most literature/books discuss sparse algorithm mainly towards symmetric matrix.)

Also, I search on Google for some literature, and find that, for symmetric, sparse , matrix, there exist some specially designed methods (sometimes towards special cases though, e.g. for tri-diagonal cases) which can obviously beat symmetric, dense/non-sparse matrix). However, I don't see any literature exactly/explicitly support my colleague's comment for general case,i.e., non-symmetric, dense matrix.

The sparse pattern of A matrix is shown as follows: The sparse pattern of A matrix

References:

[ref1] S. H. Lui, H. B. Keller Y, T. W. C. Kwok. Homotopy Method For The Large Sparse Real Nonsymmetric Eigenvalue Problem.

[ref2] Eigenvalue computation for sparse matrices. http://dispense.dmsa.unipd.it/ferronato/MN-PhD/2008/eigen.pdf

[ref3] Chapter.4 Nonsymmetric Eigenvalue Problems. Applied Numerical Linear Algebra. 1997, 139-193.

[ref4] https://web.stanford.edu/class/cme335/lecture4sup.pdf

$\endgroup$
  • $\begingroup$ as given, $A$ is not square. what do you mean by eigenvalues then? $\endgroup$ – Dima Pasechnik Jan 11 at 21:29
  • $\begingroup$ A is square, 2n-by-2n, composed of 4 n-by-n matrix, you may need to look at the description carefully. $\endgroup$ – ZPascal Jan 11 at 21:49
  • $\begingroup$ this site uses mathematical notation for matrices, not Matlab... $\endgroup$ – Dima Pasechnik Jan 12 at 6:15
  • $\begingroup$ anybody who does not know matlab would have no clues about the difference between comma and semicolon in your notation. $\endgroup$ – Dima Pasechnik Jan 12 at 6:17
  • $\begingroup$ I edited the beginnig of the question to give you an idea how it is meant to be done. $\endgroup$ – Dima Pasechnik Jan 12 at 6:28
0
$\begingroup$

The remark of your coworker is only valid if you significantly increase the number of non-0 entries in your halved matrix.

I presume you used a form of Schur complement trick to halve the size.

And if you wrote it down one would have seen that the number of non-0 in the result only went down. Thus, it could only make it faster to compute eigenvalues.

$\endgroup$
  • $\begingroup$ Thank you so much. One more question, would you please provide any published references/literature/book chapters regarding your above comments? so that I can use them to convince my coworker. Thanks again. $\endgroup$ – ZPascal Jan 13 at 4:08
  • $\begingroup$ it is just common sense. Without a complete description of the transformation you use, it is hard to say more. $\endgroup$ – Dima Pasechnik Jan 13 at 8:30
  • $\begingroup$ My transformation is basically what you mentioned: Shur complement. $\endgroup$ – ZPascal Jan 13 at 19:18
  • $\begingroup$ well, it's hard to give a reference to an obvious. As long as your transformation does not involve substantial growth in magnitudes of the entries (e.g. from a 0-1 matrix you get a matrix with entries from -10000 to +10000) you should only get an improvement in performance. $\endgroup$ – Dima Pasechnik Jan 13 at 21:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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