Abstract: Communication algorithms need to exchange data between adjacent subdomains. The detection of adjacent subdomains is an import task for communication algorithms, which can be done by solving an intersection problem of boxes. An interval tree algorithm is proposed for intersection problems. Taking advantage of structured mesh applications, it is able to maintain 0 (Nlog N) time complexity. Numerical experiments show that the algorithm is able to achieve high computational efficiency and good scalability. It supports parallel computing of miUion-box scale.

Key words: parallel computing, parallel structured mesh application, fast communication algorithm, interval tree