TransWikia.com

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

Computational Science Asked on August 22, 2021

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?

One 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.

Answered by Abdullah Ali Sivas on August 22, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP