The problem
When students learn to code FEM, they are usually not taught about sparse matrices. This is done to keep the code as well as the learning simple. Students are first taught how to code FEM, and then once they have to handle real problems, they are taught about sparse matrix operations. But unfortunately, most of the time, the semester ends without introducing sparse matrices, their importance and how to code them.
You can not even imagine solving medium to large-scale systems without sparse matrices.
Real world systems are usually somewhere between a few thousand to well over a million degrees of freedom (). What this means is that the resulting matrix in the mathematical model of the system will be . Luckily in the FEM, the matrices are usually sparse and we can solve for a big system. But most researchers do not understand how the size of the system is related to the computers ability to solve it.
Lets try to understand this:
- Every number takes a certain amount of RAM space. Remember 1 byte = 8 bits and
| Data Type | Size | Description |
|---|---|---|
| byte | 1 byte | -128 to 127 |
| short | 2 bytes | -32,768 to 32,767 |
| int | 4 bytes | -2,147,483,648 to 2,147,483,647 |
| long | 8 bytes | -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 |
| float | 4 bytes | Stores fractional numbers. Sufficient for storing 6 to 7 decimal digits |
| double | 8 bytes | Stores fractional numbers. Sufficient for storing 15 decimal digits |
| boolean | 1 bit | Stores true or false values |
| char | 2 bytes | Stores a single character/letter or ASCII values |
-
In general we work with
double(8 bytes) data type to store data and withint(4 bytes) to store indexes. -
1MB = 1e6 Bytes
-
1GB = 1e9 Bytes = 1000 MB
-
1TB = 1e12 Bytes = 1000 GB
-
Considering a
tridiagonal systemwhere we have non zero entities only on the main diagonal and adjacent to it here is a comparison of RAM requirement for dense v/s sparse system.RAM for dense storage: GB
RAM for sparse storage: GB
dof Num items RAM for Dense RAM for Sparse 1000 1 Million 8 MB 0.048 MB 10,000 1e8 800 MB 0.48 MB 1 Lakh 1e10 80 GB 🧐 4.8 MB 1 Million 1e12 8 TB 😨 48 MB 10 Million 1e14 800 TB 😱 480 MB 100 Million 1e16 0.8 Million TB 🤯 4.8 GB 1 Billion 1e18 80 Million TB ☠️ 48 GB -
The above table is formed by considering that every cell of the matrix will hold a double value (8 bytes) and the indices are stored as integers (4 bytes) for the sparse matrix. A sparse matrix is stored as a 3 column matrix with first column being
datathe second beingrow numberand the third beingcolumn number. -
Thus you can see that by using a dense matrix you will exhaust you laptop memory even with a 1Lakh dof system.
The solution
If you are a researcher working with matrices, you should learn and understand how to work with sparse matices. It is the only way to solve large systems on your computer. There is no other alternative.