Vectorization of solution algorithms for certain integral equations (Q1842723)

The common method for the solution of the second-kind Fredholm integral equation \[ y(x) = \int^ T_ 0 K(x,t) y(t) dt + f(x); \tag{1} \] \(0 \leq x \leq 1\), in case of a smooth kernel is the approximate reduction of the equation by quadrature formulas to an algebraic system with an \(N \times N\) matrix (where \(N\) is the number of discretization points). The numerical implementation of this procedure requires a minimal memory capacity of \(O(N^ 2)\) and a number of operations \(O(N^ 3)\) \((N \to \infty)\). In the case of a difference kernel \(K = K(x-t)\), these values are significantly decreased: memory capacity \(O(N)\) and operations number \(O(N^ 2)\) are required. Similar characteristics can be obtained for ``almost difference'' kernels or difference-sum kernels. A more general class of kernels which satisfy (2) \(\left( {\partial^ 3 \over \partial x^ 3} + {\partial^ 3\over \partial t^ 3}\right) K(x,t) = 0\), lead to a numerical implementation for the solution of (1) of comparable magnitude. Similar computational characteristics can also be obtained for kernels \(K\) which satisfy fourth-order equations. Much attention is currently paid to algorithms implemented in multiprocessor systems. For algebraic systems with an \(N \times N\) matrix, the Gauss-Jordan method makes it possible to complete parallel computations on \(N^ 2\) processors within \(N\) cycles. In the Toeplitz case (i.e., at \(K = K(x,t)\)), we can activate \(O(N)\) processors with the same \(N\) cycles, which requires drastic modification of the algorithm. In this paper we obtain similar characteristics in principle for kernels of type (2).