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

Question

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?

Abdullah Ali Sivas · 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.

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

One Answer

Add your own answers!

Ask a Question