4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Maxim Umansky Jul 21 '20 at 13:50
  • $\begingroup$ Sparse and dense in n this context simply refer to the Jacobian. $\endgroup$ – David Ketcheson Jul 23 '20 at 7:57
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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