Upscaling, Basis Optimization, and Darcy Flow Finite Element Basis Optimization for Darcy Flow Simulation of flow through a heterogeneous porous medium with fine-scale features can be computationally expensive if the flow is fully resolved. Coarsening the problem gives a faster approximation of the flow but at a cost of some detail. We propose an algorithm that obtains the fully resolved approximation but only iterates on a sequence of coarsened problems. The sequence is chosen by optimizing the shapes of the coarse finite element basis, and converges superlinearly. A novel iterative algorithm with quadratic convergence on a linear problem is proposed. The problem is to solve a linear system from mixed finite element methods applied to a linear elliptic PDE (Darcy flow through a porous medium). The fast convergence is acheived by considering a sequence of upscaled problems; the sequence converges to an upscaled problem whose solution coincides with the non-upscaled problem. A novel iterative algorithm is proposed for solving linear systems arising from mixed finite element methods applied to a linear elliptic PDE. The algorithm has quadratic convergence on this linear problem. The fast convergence is acheived by considering a sequence of upscaled problems; the sequence converges to an upscaled problem whose solution coincides with the non-upscaled problem. \begin{abstract} The proposed research for the Computational and Applied Mathematics Ph.~D. degree is to use innovative improvements to and applications of a variational multiscale subgrid upscaling procedure to greatly reduce the time needed to simulate Darcy flow problems. Additionally, these techniques are sufficiently abstract to be applied to other model physical problems with likely success. Simulation of flow through a porous medium on a large scale can be computationally expensive if the flow is resolved at a fine scale. Numerous techniques have been proposed to ``upscale'' the problem so that computations can be performed on a coarser scale but still retain information about the fine-scale flow and problem data. We use one kind of upscaling --- variational multiscale subgrid upscaling --- to construct preconditioners for solving the full fine-scale problem. In one preconditioning method, multigrid techniques are used to form a two-level iterative scheme with a fine-scale smoother as one level, and the upscaling preconditioner as the second level. Like multigrid, this scheme has a convergence factor dependent on both the permeability field (the ratio of maximum to minimum values) and the relative resolution of the fine and coarse grids. However, the upscaling preconditioner is much more effective at capturing the correct coarse-scale behavior than a coarse-scale smoother (as used in multigrid). Further, the upscaling preconditioner has an operation count similar to that of multigrid, and the extra subgrid computations exhibit perfect parallelism. In another method, the coarse basis for the variational multiscale subgrid upscaling is modified to allow the possibility of the upscaled solution coinciding with the full fine-scale solution. Starting with the ordinary upscaling solution, iterative nonlinear optimization techniques are applied to update the basis for the upscaling problem. Under suitable conditions, the modified upscaled solution will converge superlinearly to the fine-scale solution. The method only requires solving upscaled problems (an ``inexpensive'' operation) and some matrix-vector multiplies to find the residual of the fine-scale problem. The proposed research is multidisciplinary and requires developments and understanding in mathematics, computer science, and engineering. Although there is a degree of overlap between the problems studied and methods used in these disciplines, some goals specific to each area are listed below. \textbf{Area A:} A-priori error analysis of finite element methods as applied to linear elliptic partial differential equations will be a necessary element to show convergence of the proposed methods. For the two-level method we need to develop error estimates for the smoothing and approximation properties. For the nonlinear method we need to find the relationship between the error in the extra degrees of freedom and the error in the related modified upscaled problem. An appropriate norm for the error in the extra degrees of freedom is needed (perhaps they can be viewed as traces of fluxes on coarse cell boundaries). \textbf{Area B:} Research of analysis of convergence of iterative schemes for solving large, sparse linear systems is necessary. Both methods use Schur complement techniques (on both subgrid problems and velocities), and (preconditioned) conjugate gradient and Krylov ideas. The two-level scheme requires analysis of smoothers and the performance of a multigrid-like scheme. The nonlinear method requires study of the details of Newton, quasi-Newton, and secant methods. For each of these three, the problem of global convergence needs to be addressed. For the quasi-Newton methods, there is also the choice of approximation to the Jacobian and how it is factored. For the secant method there are the issues of QR updates, the choice of initialization of the approximate Jacobian, and the bounded deterioration of it. Consideration needs to be made of high performance computing and parallelism concerns when designing and implementing algorithms. \textbf{Area C:} Efficient, accurate Darcy flow simulations are the prime motivation for this research. We need to detail the performance of the proposed algorithms in different geostatistical settings to guide practitioners' use. We need to be able to say how quickly and how well we can approximate large-scale features of the flow. We want to know if long-range correlations in the problem data present any theoretical or practical difficulties for the algorithms, and be able to present some engineering conclusions about the effect of such correlations on flow. We need to provide a well-documented implementation of the proposed algorithms in parallel for three dimensional problems (and perhaps extend it to handle two-phase miscible and/or immiscible displacements). It should be able to model both rate wells and Peaceman bottom-hole-pressure wells. \end{abstract} \begin{abstract} Simulation of flow through a heterogeneous porous medium with fine-scale features can be computationally expensive if the flow is fully resolved. Multigrid algorithms are often used to compute approximations to such problems because of storage considerations, the high condition number of the problem, and multigrid's resolution independent convergence rate. The proposed algorithm takes an ordinary multigrid method and replaces the coarsening procedure with an upscaling one. Upscaling aims for performing computations on a coarser scale but still retaining information about the fine-scale flow and problem data. That is, an upscaled computation is just as cheap as a coarse one, but much more accurate. By replacing coarsening with upscaling in multigrid, faster convergence ensues. %A far better approximation usually results, but as with an ordinary coarsening, %upscaling may still not produce a satisfactory approximation on its own, and an %approximation to the full fine-scale problem is necessary. Numerous upscaling techniques have been proposed; variational multiscale subgrid upscaling is used here. By keeping within the usual finite element variational framework, known multigrid analysis techniques can be applied. Like multigrid, the proposed scheme has a convergence factor dependent on both the permeability field (the ratio of maximum to minimum values) and the relative resolution of the fine and coarse grids. %However, the upscaling preconditioner is much more effective at %capturing the correct coarse-scale behavior than a coarse-scale smoother (as %used in multigrid). Further, the upscaling preconditioner has an operation %count similar to that of multigrid, and the extra subgrid computations exhibit %perfect parallelism. subgrid solve only once per simulation, not per %iteration, too. \end{abstract}