|Fast methods H-matrices FFT integral operators Volterra operators|
Population dynamic models play a important role in scientific and industrial work. This models are mostly characterised by a population balance equation based on a system of integro differential equations. The integral operators can be distinguished in linear and quadratic integral opearators. A naive approach in the Galerkin discretisation of this Volterra integral operators leads to a quadratic complexity (O(n^2)) for creation, storage and evaluation of the belonging system matrices.
In this work techniques based on H-matrices and FFT, are introduced to approximate the system matrices with an almost linear complexity (O(n) or O(n log n)).
Basic idea of the calculus of H-matrices is the local approximation of the underlying kernel functions by separable kernel expansions. Then a blockwise low rank representation of the system matrix can be achieved. With the help of important examples of kernel functions an admissibility condition is formulated to control the approximation error of the kernel expansion. This works well for the linear integral operators, here a complexity of O(n) could be reached. For the Volterra boundaries a special approach has been used.
In the case of the quadratic operator a combination of H-matrix techniques and equidistant quadrature rule is introduced. This leads to a blockwise approximation of the system matrix by sums of Toeplitz matrices. Here a different admissibilty condition is needed. The storage of a Toeplitz matrix can be done also with O(n). For matrix-vector-multiplication FFT is used what can be done with O(n log n). Before every multiplication an update of the system matrix is necessary. The complexity of the update for one matrix block is also O(n). The overall complexity for the quadratic operator is O(n log n) for storage, update and creation, for the matrix-vector multiplication the complexity is O(n log^2 n).