2
$\begingroup$

I have some questions about diagonalizing matrices. My interest lies in computing all eigenvalues of a given matrix. To avoid wasting time and improve my research efficiency, I want to understand the relationship between diagonalization algorithms and computer specifications.

For my current setup, I use an Apple MacBook Pro (2019) 13 with an Intel Core i7 2.8GHz processor, 16GB RAM, and 512GB SSD. I typically work with non-Hermitian matrices in Julia 1.8 using LinearAlgebra.jl, which seems to call BLAS/LAPACK in its backend. Based on my experience, it appears that diagonalizing a sparse, non-Hermitian matrix of approximately 13000 by 13000 with double precision is the limit for my laptop.

Q1. How much RAM is required to diagonalize an N by N matrix with double precision? For example, 1GB for storing the input matrix, 2GB for executing the algorithm, and 1.5GB for storing the output data. I'm particularly interested in the following scenarios:
1-1: Dense and non-Hermitian matrices.
1-2: Sparse and non-Hermitian matrices.
1-3: Sparse and non-Hermitian matrices with quadruple precision.

Q2. How much time does the diagonalization process take in the above scenarios?

Q3. Which computer components (CPU, GPU, RAM, etc.) are most relevant to the performance of diagonalization? In an extreme case, if I had an Apple MacBook Pro with M3 Max (16-core CPU, 40-core GPU, 128GB RAM, 8TB SSD), one of the most high-spec laptops, would the diagonalization performance drastically improve? Additionally, is it possible to calculate a 108000 by 108000 non-Hermitian matrix on this (or any other) laptop? (I couldn't find any benchmarks regarding matrix diagonalization.)

Thank you in advance.

$\endgroup$
4
  • $\begingroup$ Do you want the eigenvectors as well? $\endgroup$
    – Ian Bush
    May 14 at 7:34
  • $\begingroup$ You might want to look into randomized linear algebra algorithms for computing eigenvalues. There may be some useful tools there you can leverage that will be especially good when you feed it sparse matrices. $\endgroup$
    – spektr
    May 15 at 5:01
  • $\begingroup$ @Ian Bush It depends. In most cases, I need all eigenvalues and only a few eigenvectors that I am interested in. $\endgroup$
    – yosuga
    May 15 at 5:12
  • $\begingroup$ @spektr any references for a beginner? $\endgroup$
    – yosuga
    May 15 at 5:14

1 Answer 1

3
$\begingroup$

I am not an expert in diagonalization, but take LU decomposition as an example:

  • It is done in-place, i.e., the only memory to speak of is the matrix itself. There is no "work space" memory of comparable size.
  • The effort is approximately $\frac 23 n^3$ floating point operations. If your matrix is symmetric (or complex hermitian) you can get away with a Cholesky decomposition, for which the effort is half that.
  • Since the matrix does not fit into the cache, everything is limited by the amount of data you can move from memory to the processor. The number of cores, the speed at which each core operates, etc., all do not matter: The only thing that matters is the bandwidth of the memory bus.

As I said, I don't know diagonalization algorithms very well, but would expect the effort to be a small multiple of the one stated above, and that everything can still be done in-place or perhaps in one copy of the matrix (if you don't just want the eigenvalues, but also all eigenvectors).

$\endgroup$
11
  • $\begingroup$ Thanks! I have two questions. With the same processor, and when there is sufficient memory and memory bandwidth to handle an input matrix (as well as its copy if needed), does the operation time of LU decomposition remain unchanged even if these resources are increased? Additionally, how much memory bandwidth is needed for LU decomposition of an n by n general matrix with double precision? $\endgroup$
    – yosuga
    May 15 at 5:06
  • $\begingroup$ The operation time is still proportional to $n^3$. As for memory bandwidth: You can't choose that. It is the same for every processor family, regardless of whether you choose the 4- or 6- or 8-core variant. Money can't buy you better bandwidth. $\endgroup$ May 15 at 12:38
  • $\begingroup$ I'm a bit confused by the latter answer. Memory bandwidth depends on the processor (family) one uses. For example, the Mac M1 chip maximally shows 68.2GB/s, while the M1 Pro exhibits 200GB/s, correct? Then, when performing LU decomposition of a matrix that requires 10GB, I guess that a processor with 5GB/s bandwidth takes twice the operation time compared to one with 10GB/s bandwidth. So, what I'm asking is, how much memory bandwidth is sufficient in this case: 10GB/s, 20GB/s, or more? $\endgroup$
    – yosuga
    May 15 at 17:51
  • 2
    $\begingroup$ @Wolfgang Bangerth Re "Money can't buy you better bandwidth". The conventional wisdom is "You can pay for bandwidth, but latency is forever". And this latter statement largely holds across several decades of personal experience. People do pay for bandwidth and it does help application performance. Your general observation that much practical large-scale computation is constrained by memory throughput rather than computational throughput (so more similar to HPCG rather than HPL) is on the dot, of course. $\endgroup$
    – njuffa
    May 16 at 21:15
  • 1
    $\begingroup$ @Wolfgang Bangerth Processors includes CPUs and GPUs. One can go from 100 GB/sec (quad-channel DDR4) in a workstation to about 3.3 TB/sec (HBM2e/HBM3) on the latest supercomputer GPUs from AMD and NVIDIA. Roughly a 32x spread. I would put a low-end workstation CPU at four cores, so a similar factor. The cost of that fast memory subsystem becomes exorbitant at the high end, but apparently there are still enough paying buyers to make it worthwhile for vendors to offer ... $\endgroup$
    – njuffa
    May 17 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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