Predicting computer run-time for the Barnes-Hut multipole method for electromagnetic scattering

This paper presents a novel simple methodology for quickly predicting and o ptimizing computer run-time for the Barnes-Hut multipole method for boundar y element electromagnetic scattering problems. The methodology is easily ex tended to other multipole methods (e.g. Greengard-Rokhlin) and to other phy sics. The novel idea is to simply count the number of element-cell interact ions, number of direct element-element interactions, and the number of cell multipole expansion creations teach expansion weighted by the number of el ements in the cell), and then finally combine these three results with the associated unit costs to obtain the total computer run-time to perform a si ngle matrix-vector multiply. By counting operations instead of actually per forming them, the time to predict the computer run-time is orders of magnit ude smaller than the time to actually perform the associated calculations. This new approach allows for very quick optimization of parameters, such as the maximum number of elements in a final generation cell of the tree. Num erical examples are presented herein in which the rate of return (time save d over time spent finding optimal parameter values) is significantly more t han two orders of magnitude. (C) 2001 Elsevier Science Ltd. All rights rese rved.