A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains (Q693189)

For approximate solving the integral equation of Fredholm type \[ a(t)q(t) + \int^{T}_{0}b(t,t')q(t')dt'= f(t), \qquad t\in [0,T], \] the method of Gaussian quadrature with nodes \(\{{t_{j}}\}^{N}_{1}\) is used. Upon discretization, the initial equation takes the form \[ Aq=f, \] where \(A\) is a dense matrix of the size \( N\times N \) and \( q=q(t_{i})\), \(f=f(t_{i})\). To solve this linear system, the direct method is used to compute the matrix \( S= A^{-1}\). In the construction of \( S \), the matrix \( A \) is presented in a ``block separable'' form and the technique of the orthonormal matrices in the factorization of \( A \) is applied. The complexity of the algorithm for inverting such a matrix is of the order \(O(n)\).