Fixed Point Computation and Parallel Algorithms for Solving Wave Equations

technical reportThis dissertation is concerned with two problems: fixed-point computation and parallel algorithms for solving wave equations. Many problems can be formulated as fixed-point problems, which is to solve the equations of the form f(x) - x = 0. We develop efficient algorithms and establish complexity results for such fixed-point computations. For univariate functions, we demonstrate Fixed Point Envelope (FP-EN) algorithms and prove that they minimize the number of function evaluations for computing an approximation to within a prescribed absolute error tolerance. For multivariate contractive functions, we exhibit a Fixed Point Ellipsoid (FP-EL) algorithm. This algorithm is much more efficient than the well-known simple iteration algorithm. We also show an upper bound on the number of function evaluations for this case. For multivariate noncontractive functions, we prove that the complexity is infinite whenever the error tolerance is less than 0.5. As the second problem, we consider the acoustic wave equation and the elastic wave equation that are frequently used in seismology. We develop parallelized finite difference algorithms for solving these equations. This is done by dividing the computational domain into subdomains and then by assigning a processor to each subdomain for computing and storing local grid data. We discuss parallel algorithms on three computing networks: processor arrays, rings, and meshes, with emphasis on the part of communication and synchronization. Finally, we demonstrate that our implementations on transputer linear arrays achieve linear speedup