# Sparse dense matrix versus non-sparse dense matrix in eigenvalue computation

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:

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.

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

## 2 Answers

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.

• 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. Jan 13, 2019 at 4:08
• it is just common sense. Without a complete description of the transformation you use, it is hard to say more. Jan 13, 2019 at 8:30
• My transformation is basically what you mentioned: Shur complement. Jan 13, 2019 at 19:18
• 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. Jan 13, 2019 at 21:59

If you take the transpose of the matrix, which has the same eigenvalues, and you divide by $$w_0$$, you get the (block) companion matrix of a quadratic matrix polynomial with $$n \times n$$ coefficients. Using an algorithm designed for such problems may save time.