# What is a dense ODE system? What is a sparse ODE system?

Can you provide a jargon-free (as much as possible) explanation of what is meant by "dense ODE systems", and "sparse ODE systems"?

Some hints I have gotten from Googling:

• dense ODE systems' computation cost increases quadratically with the size of the system

• sparse ODE systems' computation cost does not correlate with the size of the system

• dense ODE systems' computation cost is dominated by CPU considerations

• sparse ODE systems' computation cost is dominated by "communication" considerations

Some guesses of mine: if a dense ODE system's computation cost increases quadratically with the size of the system, then there must be lots of "point-point" interactions between the variables. So, would an n-body problem be dense?

I can't think of a good example of a sparse ODE system, except for the trivial one, where I take a bunch of independent ODEs which have nothing to do with each other, and then put them together claiming it is a "system"?

Why would a sparse ode system's computation cost be dominated by communication concerns? Communication between what? Processors?

• Sparse ODE system example $\dot{y_i} = \alpha (y_{i+1} - y_{i-1})$ which results from spatial discretization of PDE $\dot{y} = dy/dx$ on a 1D grid. It is called sparse because it leads to sparse matrices. – Maxim Umansky Jul 21 '20 at 13:50
• Sparse and dense in n this context simply refer to the Jacobian. – David Ketcheson Jul 23 '20 at 7:57

## 1 Answer

n-body problem would be dense (of course, if you don't do any filtering to remove "weak" couplings.

As Maxim Umansky mentioned in the comments, some discretizations of time-dependent PDEs give rise to sparse ODE systems. Some others, like spectral methods, are dense ODE systems.

In terms of parallel computing, I don't think there would be much difference in the cost of communication in the solution of sparse ODE systems vs. dense ODE systems -unless, of course, you are moving parts of the system between processes. However, algorithms for sparse ODE systems are usually less time consuming, for example take dense matrix-vector multiplication $$O(n^2)$$ against sparse matrix-vector multiplication $$O(nonzeros)$$ -and nonzeros are $$O(n)$$ by definition of sparsity. So one can imagine time spent communicating becomes important.