Complexity theory for Lie-group solvers

Commencing with a brief survey of Lie-group theory and differential equations evolving on Lie groups, we describe a number of numerical algorithms designed to respect Lie-group structure: Runge-Kutta Munthe-Kaas schemes, Fer and Magnus expansions. This is followed by derivation of the computational cost of Fer and Magnus expansions, whose conclusion is that for order four, six, and eight an appropriately discretized Magnus method is always cheaper than a Fer method of the same order. Each Lie-group method of the kind surveyed in this paper requires the computation of a matrix exponential. Classical methods, e.g., Krylov-subspace and rational approximants, may fail to map elements in a Lie algebra to a Lie group. Therefore we survey a number of approximants based on the splitting approach and demonstrate that their cost is compatible (and often superior) to classical methods. (C) 2002 Elsevier Science (USA).