Faculty & Staff Research
http://hdl.handle.net/1911/75172
2018-06-21T02:15:47ZNovel Techniques for the Zero-Forcing and p-Median Graph Location Problems
http://hdl.handle.net/1911/102254
Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems
Fast, Caleb C.
This thesis presents new methods for solving two graph location problems, the p-Median problem and the zero-forcing problem. For the p-median problem, I present a branch decomposition based method that finds the best p-median solution that is limited to some input support graph. The algorithm can be used to either find an integral solution from a fractional linear programming solution, or it can be used to improve on the solutions given by a pool of heuristics. In either use, the algorithm compares favorably in running time or solution quality to state-of-the-art heuristics. For the zero-forcing problem, this thesis gives both theoretical and computational results. In the theoretical section, I show that the branchwidth of a graph is a lower bound on its zero-forcing number, and I introduce new bounds on the zero-forcing iteration index for cubic graphs. This thesis also introduces a special type of graph structure, a zero-forcing fort, that provides a powerful tool for the analysis and modeling of zero-forcing problems. In the computational section, I introduce multiple integer programming models for finding minimum zero-forcing sets and integer programming and combinatorial branch and bound methods for finding minimum connected zero-forcing sets. While the integer programming methods do not perform better than the best combinatorial method for the basic zero-forcing problem, they are easily adapted to the connected zero-forcing problem, and they are the best methods for the connected zero-forcing problem.
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/96074
2017-05-01T00:00:00ZHermite Methods for the Simulation of Wave Propagation
http://hdl.handle.net/1911/102252
Hermite Methods for the Simulation of Wave Propagation
Vargas, Arturo
Simulations of wave propagation play a crucial role in science and engineering. In applications of geophysics, they are the engine of many seismic imaging algorithms. For electrical engineers, they can be a useful tool for the design of radars and antennas. In these applications achieving high fidelity, simulations are challenging due to the inherent issues in modeling highly oscillatory waves and the associated high computational cost of high-resolution simulations. Thus the ideal numerical method should be able to capture high-frequency waves and be suitable for parallel computing. In both seismic applications and computational electromagnetics the Yee scheme, a finite difference time domain (FDTD) method, is the method of choice for structured grids. The scheme has the benefit of being easy to implement but performs poorly in the presence of high-frequency waves. High order accurate FDTD methods may be derived but ultimately rely on neighboring grid points when approximating derivative. In contrast to FDTD methods, the Hermite methods of Goodrich and co-authors (2006) use Hermite interpolation and a staggered (dual) grid to construct high order accurate numerical methods for first order hyperbolic equations. These methods achieve high order approximations in both time and space by reconstructing local polynomials within cells of the computational domain and employing Hermite-Taylor time stepping. The resulting schemes are able to evolve the solution locally within a cell making them ideal for parallel computing. Building on the original Hermite methods this thesis focuses on two goals: (1) the development of new Hermite methods and (2) their implementation on modern computing architectures. To accomplish the first objective, this thesis presents two variations of Hermite methods which are designed to simplify the scheme while preserving the favorable features. The first variation is a family of Hermite methods which do not require a dual grid. These methods eliminate the need for storing dual coefficients while maintaining optimal convergence rates. The second type of variation are Hermite methods which use leapfrog time-stepping. These schemes propagate the solution with less computation than the original scheme and may be used for either first or second order equations. To address the second objective, this thesis presents algorithms which take advantage of the many-core architecture of graphics processing units (GPU). As threedimensional simulations can easily exceed the memory of a single GPU, techniques for partitioning the data across multiple GPUs are presented. Finally, this thesis presents numerical results and performance studies which confim the accuracy and efficiency of the proposed Hermite methods for linear and nonlinear wave equations.
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/96153
2017-05-01T00:00:00ZGPU-Accelerated Discontinuous Galerkin Methods on Hybrid Meshes: Applications in Seismic Imaging
http://hdl.handle.net/1911/102250
GPU-Accelerated Discontinuous Galerkin Methods on Hybrid Meshes: Applications in Seismic Imaging
Wang, Zheng
Seismic imaging is a geophysical technique assisting in the understanding of subsurface structure on a regional and global scale. With the development of computer technology, computationally intensive seismic algorithms have begun to gain attention in both academia and industry. These algorithms typically produce high-quality subsurface images or models, but require intensive computations for solving wave equations. Achieving high-fidelity wave simulations is challenging: first, numerical wave solutions may suffer from dispersion and dissipation errors in long-distance propagations; second, the efficiency of wave simulators is crucial for many seismic applications. High-order methods have advantages of decreasing numerical errors efficiently and hence are ideal for wave modelings in seismic problems. Various high order wave solvers have been studied for seismic imaging. One of the most popular solvers is the finite difference time domain (FDTD) methods. The strengths of finite difference methods are the computational efficiency and ease of implementation, but the drawback of FDTD is the lack of geometric flexibility. It has been shown that standard finite difference methods suffer from first order numerical errors at sharp media interfaces. In contrast to finite difference methods, discontinuous Galerkin (DG) methods, a class of high-order numerical methods built on unstructured meshes, enjoy geometric flexibility and smaller interface errors. Additionally, DG methods are highly parallelizable and have explicit semi-discrete form, which makes DG suitable for large-scale wave simulations. In this dissertation, the discontinuous Galerkin methods on hybrid meshes are developed and applied to two seismic algorithms---reverse time migration (RTM) and full waveform inversion (FWI). This thesis describes in depth the steps taken to develop a forward DG solver for the framework that efficiently exploits the element specific structure of hexahedral, tetrahedral, prismatic and pyramidal elements. In particular, we describe how to exploit the tensor-product property of hexahedral elements, and propose the use of hex-dominant meshes to speed up the computation. The computational efficiency is further realized through a combination of graphics processing unit (GPU) acceleration and multi-rate time stepping. As DG methods are highly parallelizable, we build the DG solver on multiple GPUs with element-specific kernels. Implementation details of memory loading, workload assignment and latency hiding are discussed in the thesis. In addition, we employ a multi-rate time stepping scheme which allows different elements to take different time steps. This thesis applies DG schemes to RTM and FWI to highlight the strengths of the DG methods. For DG-RTM, we adopt the boundary value saving strategy to avoid data movement on GPUs and utilize the memory load in the temporal updating procedure to produce images of higher qualities without a significant extra cost. For DG-FWI, a derivation of the DG-specific adjoint-state method is presented for the fully discretized DG system. Finally, sharp media interfaces are inverted by specifying perturbations of element faces, edges and vertices.
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/96151
2017-05-01T00:00:00ZAn Inverse Free Projected Gradient Descent Method for the Generalized Eigenvalue Problem
http://hdl.handle.net/1911/102255
An Inverse Free Projected Gradient Descent Method for the Generalized Eigenvalue Problem
Camacho, Frankie
The generalized eigenvalue problem is a fundamental numerical linear algebra problem whose applications are wide ranging. For truly large-scale problems, matrices themselves are often not directly accessible, but their actions as linear operators can be probed through matrix-vector multiplications. To solve such problems, matrix-free algorithms are the only viable option. In addition, algorithms that do multiple matrix-vector multiplications simultaneously (instead of sequentially), or so-called block algorithms, generally have greater parallel scalability that can prove advantageous on highly parallel, modern computer architectures. In this work, we propose and study a new inverse-free, block algorithmic framework for generalized eigenvalue problems that is based on an extension of a recent framework called eigpen|an unconstrained optimization formulation utilizing the Courant Penalty function. We construct a method that borrows several key ideas, including projected gradient descent, back-tracking line search, and Rayleigh-Ritz (RR) projection. We establish a convergence theory for this framework. We conduct numerical experiments to assess the performance of the proposed method in comparison to two well-known existing matrix-free algorithms, as well as to the popular solver arpack as a benchmark (even though it is not matrix-free). Our numerical results suggest that the new method is highly promising and worthy of further study and development.
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/96001
2017-05-01T00:00:00Z