Multivariate integration on hypercubic and mesh networks

✍ Scribed by Elise de Doncker; Ajay Gupta

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 252 KB
• Volume: 24
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(98)00056-8

✦ Synopsis

We analyze a class of adaptive algorithms for integration over x-dimensional hyper-rectangular or simplical regions, on distributed systems. An adaptive algorithm attempts to achieve the requested accuracy by re®ning the subdivision of the integration region, thus allowing for a concentration of subdivisions near singularities. At the subdivision of a region, the error behaves according to a prescribed model, relating the error of the parent region to that of its children. The analysis can also be applied to problems in other areas, as long as the task selection is based on a priority function which behaves according to a suitable model. Using an ecient management of the subregions, we show that an Opa log p speedup can be achieved on a p-processor hypercubic network, such as shue exchange, butter¯y and hypercube. Furthermore, a speedup of O p p can be achieved on a p p  p p mesh network.

We also show that our algorithms compare favorably with well-known dynamic load balancing strategies.