# 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? – Dima Pasechnik Jan 11 '19 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. – ZPascal Jan 11 '19 at 21:49
• this site uses mathematical notation for matrices, not Matlab... – Dima Pasechnik Jan 12 '19 at 6:15
• anybody who does not know matlab would have no clues about the difference between comma and semicolon in your notation. – Dima Pasechnik Jan 12 '19 at 6:17
• I edited the beginnig of the question to give you an idea how it is meant to be done. – Dima Pasechnik Jan 12 '19 at 6:28