Rice Header
CAAM Header

Technical Reports (2016)

TR16-06          PDF File

Optimal Control of Flow and Transport Equations Using Discontinuous Galerkin Methods
Brianna Lynn

This thesis analyzes the accuracy of discontinuous Galerkin methods for solving optimal control problems for flow and transport equations. The optimality conditions for each optimal control problem and error estimates for an optimal control problem constrained by a system of steady-state partial differential equations are derived. Synthetic data is used to create numerical examples that verify the methods work. Then the optimality conditions for the optimal control of the miscible displacement equations, where the control is the flow rate of the injection fluid, are derived.

May 2016


TR16-05          PDF File

Black Oil Simulation Utilizing a Central Finite Volume Scheme
Rujeko Chinomona

Black-oil simulation is a valuable tool in predicting the multi-phase multi-component flow of fluids in reservoirs. This research validates the use of a central high resolution finite volume scheme developed by Kurganov and Tadmor (KT) to the black-oil model problem. The KT scheme is desirable because of its relative ease of implementation and its ability to generate high resolution solutions at low computational costs. In addition, convergence rates on simple hyperbolic conservation law problems provided in this thesis indicate that the KT scheme is second order. Results obtained from simulations are in alignment with published literature and simulations also accommo- date changing variables with predictable outcomes. The KT scheme can be applied to the black-oil model problem with increased confidence.

May 2016


TR16-04          PDF File

Nonnormality in Lyapunov Equations
Jonathan Baker

The singular values of the solution to a Lyapunov equation determine the potential accuracy of the low-rank approximations constructed by iterative methods. Low-rank solutions are more accurate if most of the singular values are small, so a-priori bounds that describe coefficient matrix properties that correspond to rapid singular value decay are valuable. Previous bounds take similar forms, all of which weaken (quadratically) as the coefficient matrix departs from normality. Such bounds suggest that the farther from normal the coefficient matrix is, the slower the singular values of the solution will decay. This predicted slowing of decay is manifest in the ADI algorithm for solving Lyapunov equations, which converges more slowly when the coefficient is far from normal. However, simple examples typically exhibit an eventual acceleration of decay if the coefficient departs sufficiently from normality. This thesis shows that the decay acceleration principle is universal: decay always improves as departure from normality increases beyond a given threshold, specifically, as the numerical range of the coefficient matrix extends farther into the right half-plane. The concluding chapter gives examples showing that similar behavior can occur for general Sylvester equations, though the right-hand side plays a more important role.

May 2016


TR16-03          PDF File

Clique Generalizations and Related Problems
Cynthia Ivette Wood

A large number of real-world problems can be model as optimization problems in graphs. The clique model was introduced to aid the study of network structure for social interaction. Each vertex represented an actor and the edges represented the relations between them. Nevertheless, the model has been shown to be restrictive for modeling real-world problems, since it leaves out subgraphs that do not have all possible edges. As a consequence, clique generalizations were introduced to overcome the disadvantages of the clique model. In this thesis, I present three computationally difficult combinatorial optimization problems related to clique generalization problems: co-2-plexes and k-cores.

A k-core is a subgraph with minimum degree greater than or equal to k. In this work, I discuss the minimal k-core problem and the minimum k-core problem. I present a backtracking algorithm to find all minimal k-cores of a given undirected graph and its applications to the study of associative memory. The proposed method is a modification of the Bron and Kerbosch algorithm for finding all cliques of an undirected graph. In addition, I study the polyhedral structure of the k-core polytope. The minimum k-core problem is modeled as a binary integer program and relaxed as a linear program. Since the relaxation yields to a non-integral solution, cuts must be added in order to improve the solution. I show that edge and cycle transversals of the graph give valid inequalities for the convex hull of k-cores.

A set of pairwise non-adjacent vertices defines a stable set. A stable set is the complement of a clique. A co-2-plex is a subgraph with degree less than or equal to one, and it is a stable set relaxation. I introduce a study of the maximum weighted co-2-plex (MWC2P) problem for {claw, bull}-free graphs and present two polynomial time algorithms to solve it. One of the algorithms transforms the original graph to solve an instance of the maximum weighted stable set problem utilizing Minty’s algorithm. The second algorithm is an extension of Minty’s algorithm and solves the problem in the original graph.

All the algorithms discussed in this thesis were implemented and tested. Numerical results are provided for each one of them.

May 2016


TR16-02          PDF File

Born Waveform Inversion in Shot Coordinate Domain
Yin Huang

The goal of this thesis is to integrate Born waveform inversion, variable projection algorithm and model extension concept to get a method that can improve the long scale background model updates reliably and efficiently from seismic data.

Born waveform inversion is a partially linearized version of full waveform inversion based on Born (linearized) modeling, in which the earth model is separated into a smooth long scale background model and an oscillatory short scale reflectivity and both are updated to fit observed trace data. Because kinematic variables (background model) are updated, Born waveform inversion has the same feature as full waveform inversion: very sensitive to initial model when solved by gradient based optimization method (almost the only possible method because of the problem scale). Extended Born waveform inversion allows reflectivity to depend on additional parameters, potentially enlarging the convexity domain by enlarging the searching model space and permitting data fit throughout the inversion process and in turn reducing the sensitivity to initial model.

Extended or not, the Born waveform inversion objective function is quadratic in the reflectivity, so that a nested optimization approach is available: minimize over reflectivity in an inner stage, then minimize the background-dependent result in a second, outer stage, which results in a reduced objective function of the background model only (VPE method). This thesis integrates the nested optimization approach into an inversion scheme and analyzes that the accuracy of the solution to the inner optimization is crucial for a robust outer optimization and both model extension and the nested optimization are necessary for a successful Born waveform inversion. And then we propose a flexibly preconditioned least squares migration scheme (FPCG) that significantly improves the convergence of iterative least squares migration and produces high resolution images with balanced amplitude. The proposed scheme also improves the efficiency of the solution to the inner stage of the nested optimization scheme and the accuracy of the gradient, and thus potentially improves the efficiency of the VPE method. However, a theoretical error estimate in the gradient computation of the VPE method is still hard to obtain, and we explain the reason and illustrate with numerical examples.

May 2016


TR16-01          PDF File

Accelerating Convergence by Augmented Rayleigh-Ritz Projections For Large-Scale Eigenpair Computation
Zaiwen Wen and Yin Zhang

Iterative algorithms for large-scale eigenpair computation are mostly based subspace projections consisting of two main steps: a subspace update (SU) step that generates bases for approximate eigenspaces, followed by a Rayleigh-Ritz (RR) projection step that extracts approximate eigenpairs. A predominant methodology for the SU step makes use of Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner. On the other hand, block methods such as the classic (simultaneous) subspace iteration, allow higher levels of concurrency than what is reachable by Krylov subspace methods, but may suffer from slow convergence. In this work, we analyze the rate of convergence for a simple block algorithmic framework that combines an augmented Rayleigh-Ritz (ARR) procedure with the subspace iteration. Our main results are Theorem 4.5 and its corollaries which show that the ARR procedure can provide significant accelerations to convergence speed. Our analysis will offer useful guidelines for designing and implementing practical algorithms from this framework.

January 2016

Department of Computational and Applied Mathematics
6100 Main MS-134   Houston, TX 77005   713.348.4805

Rice University   |   School of Engineering   |   J. Joyce Young Memorial Fund   |   Pearlman Memorial Fund   |   Weiser Memorial Fund   |   Contact