Numerical methods for ill-posed, linear problems

A means of assessing the effectiveness of methods used in the numerical solution of various linear ill-posed problems is outlined. Two methods: Tikhonov' s method of regularization and the quasireversibility method of Lattès and Lions are appraised from this point of view.

In the former method, Tikhonov provides a useful means for incorporating a constraint into numerical algorithms. The analysis suggests that the approach can be generalized to embody constraints other than those employed by Tikhonov. This is effected and the general "T-method" is the result.

A T-method is used on an extended version of the backwards heat equation with spatially variable coefficients. Numerical computations based upon it are performed.

The statistical method developed by Franklin is shown to have an interpretation as a T-method. This interpretation, although somewhat loose, does explain some empirical convergence properties which are difficult to pin down via a purely statistical argument.

Numerical solution of parabolic equations by the box scheme

The box scheme proposed by H. B. Keller is a numerical method for solving parabolic partial differential equations. We give a convergence proof of this scheme for the heat equation, for a linear parabolic system, and for a class of nonlinear parabolic equations. Von Neumann stability is shown to hold for the box scheme combined with the method of fractional steps to solve the two-dimensional heat equation. Computations were performed on Burgers' equation with three different initial conditions, and Richardson extrapolation is shown to be effective.

Bifurcation theory of nonlinear boundary value problems

The theory of bifurcation of solutions to two-point boundary value problems is developed for a system of nonlinear first order ordinary differential equations in which the bifurcation parameter is allowed to appear nonlinearly. An iteration method is used to establish necessary and sufficient conditions for bifurcation and to construct a unique bifurcated branch in a neighborhood of a bifurcation point which is a simple eigenvalue of the linearized problem. The problem of bifurcation at a degenerate eigenvalue of the linearized problem is reduced to that of solving a system of algebraic equations. Cases with no bifurcation and with multiple bifurcation at a degenerate eigenvalue are considered.

The iteration method employed is shown to generate approximate solutions which contain those obtained by formal perturbation theory. Thus the formal perturbation solutions are rigorously justified. A theory of continuation of a solution branch out of the neighborhood of its bifurcation point is presented. Several generalizations and extensions of the theory to other types of problems, such as systems of partial differential equations, are described.

The theory is applied to the problem of the axisymmetric buckling of thin spherical shells. Results are obtained which confirm recent numerical computations.

Dirac spectra, summation formulae, and the spectral action

Noncommutative geometry is a source of particle physics models with matter Lagrangians coupled to gravity. One may associate to any noncommutative space (A, H, D) its spectral action, which is defined in terms of the Dirac spectrum of its Dirac operator D. When viewing a spin manifold as a noncommutative space, D is the usual Dirac operator. In this paper, we give nonperturbative computations of the spectral action for quotients of SU(2), Bieberbach manifolds, and SU(3) equipped with a variety of geometries. Along the way we will compute several Dirac spectra and refer to applications of this computation.

Synthetic molecular machines for active self-assembly : prototype algorithms, designs, and experimental study

Computer science and electrical engineering have been the great success story of the twentieth century. The neat modularity and mapping of a language onto circuits has led to robots on Mars, desktop computers and smartphones. But these devices are not yet able to do some of the things that life takes for granted: repair a scratch, reproduce, regenerate, or grow exponentially fast–all while remaining functional.

This thesis explores and develops algorithms, molecular implementations, and theoretical proofs in the context of “active self-assembly” of molecular systems. The long-term vision of active self-assembly is the theoretical and physical implementation of materials that are composed of reconfigurable units with the programmability and adaptability of biology’s numerous molecular machines. En route to this goal, we must first find a way to overcome the memory limitations of molecular systems, and to discover the limits of complexity that can be achieved with individual molecules.

One of the main thrusts in molecular programming is to use computer science as a tool for figuring out what can be achieved. While molecular systems that are Turing-complete have been demonstrated [Winfree, 1996], these systems still cannot achieve some of the feats biology has achieved.

One might think that because a system is Turing-complete, capable of computing “anything,” that it can do any arbitrary task. But while it can simulate any digital computational problem, there are many behaviors that are not “computations” in a classical sense, and cannot be directly implemented. Examples include exponential growth and molecular motion relative to a surface.

Passive self-assembly systems cannot implement these behaviors because (a) molecular motion relative to a surface requires a source of fuel that is external to the system, and (b) passive systems are too slow to assemble exponentially-fast-growing structures. We call these behaviors “energetically incomplete” programmable behaviors. This class of behaviors includes any behavior where a passive physical system simply does not have enough physical energy to perform the specified tasks in the requisite amount of time.

As we will demonstrate and prove, a sufficiently expressive implementation of an “active” molecular self-assembly approach can achieve these behaviors. Using an external source of fuel solves part of the the problem, so the system is not “energetically incomplete.” But the programmable system also needs to have sufficient expressive power to achieve the specified behaviors. Perhaps surprisingly, some of these systems do not even require Turing completeness to be sufficiently expressive.

Building on a large variety of work by other scientists in the fields of DNA nanotechnology, chemistry and reconfigurable robotics, this thesis introduces several research contributions in the context of active self-assembly.

We show that simple primitives such as insertion and deletion are able to generate complex and interesting results such as the growth of a linear polymer in logarithmic time and the ability of a linear polymer to treadmill. To this end we developed a formal model for active-self assembly that is directly implementable with DNA molecules. We show that this model is computationally equivalent to a machine capable of producing strings that are stronger than regular languages and, at most, as strong as context-free grammars. This is a great advance in the theory of active self- assembly as prior models were either entirely theoretical or only implementable in the context of macro-scale robotics.

We developed a chain reaction method for the autonomous exponential growth of a linear DNA polymer. Our method is based on the insertion of molecules into the assembly, which generates two new insertion sites for every initial one employed. The building of a line in logarithmic time is a first step toward building a shape in logarithmic time. We demonstrate the first construction of a synthetic linear polymer that grows exponentially fast via insertion. We show that monomer molecules are converted into the polymer in logarithmic time via spectrofluorimetry and gel electrophoresis experiments. We also demonstrate the division of these polymers via the addition of a single DNA complex that competes with the insertion mechanism. This shows the growth of a population of polymers in logarithmic time. We characterize the DNA insertion mechanism that we utilize in Chapter 4. We experimentally demonstrate that we can control the kinetics of this re- action over at least seven orders of magnitude, by programming the sequences of DNA that initiate the reaction.

In addition, we review co-authored work on programming molecular robots using prescriptive landscapes of DNA origami; this was the first microscopic demonstration of programming a molec- ular robot to walk on a 2-dimensional surface. We developed a snapshot method for imaging these random walking molecular robots and a CAPTCHA-like analysis method for difficult-to-interpret imaging data.

Interacting single atoms with nanophotonics for chip-integrated quantum networks

Underlying matter and light are their building blocks of tiny atoms and photons. The ability to control and utilize matter-light interactions down to the elementary single atom and photon level at the nano-scale opens up exciting studies at the frontiers of science with applications in medicine, energy, and information technology. Of these, an intriguing front is the development of quantum networks where N >> 1 single-atom nodes are coherently linked by single photons, forming a collective quantum entity potentially capable of performing quantum computations and simulations. Here, a promising approach is to use optical cavities within the setting of cavity quantum electrodynamics (QED). However, since its first realization in 1992 by Kimble et al., current proof-of-principle experiments have involved just one or two conventional cavities. To move beyond to N >> 1 nodes, in this thesis we investigate a platform born from the marriage of cavity QED and nanophotonics, where single atoms at ~100 nm near the surfaces of lithographically fabricated dielectric photonic devices can strongly interact with single photons, on a chip. Particularly, we experimentally investigate three main types of devices: microtoroidal optical cavities, optical nanofibers, and nanophotonic crystal based structures. With a microtoroidal cavity, we realized a robust and efficient photon router where single photons are extracted from an incident coherent state of light and redirected to a separate output with high efficiency. We achieved strong single atom-photon coupling with atoms located ~100 nm near the surface of a microtoroid, which revealed important aspects in the atom dynamics and QED of these systems including atom-surface interaction effects. We present a method to achieve state-insensitive atom trapping near optical nanofibers, critical in nanophotonic systems where electromagnetic fields are tightly confined. We developed a system that fabricates high quality nanofibers with high controllability, with which we experimentally demonstrate a state-insensitive atom trap. We present initial investigations on nanophotonic crystal based structures as a platform for strong atom-photon interactions. The experimental advances and theoretical investigations carried out in this thesis provide a framework for and open the door to strong single atom-photon interactions using nanophotonics for chip-integrated quantum networks.

Ghosts of order on the frontier of chaos

What kinds of motion can occur in classical mechanics? We address this question by looking at the structures traced out by trajectories in phase space; the most orderly, completely integrable systems are characterized by phase trajectories confined to low-dimensional, invariant tori. The KAM theory examines what happens to the tori when an integrable system is subjected to a small perturbation and finds that, for small enough perturbations, most of them survive.

The KAM theory is mute about the disrupted tori, but, for two-dimensional systems, Aubry and Mather discovered an astonishing picture: the broken tori are replaced by "cantori," tattered, Cantor-set remnants of the original invariant curves. We seek to extend Aubry and Mather's picture to higher dimensional systems and report two kinds of studies; both concern perturbations of a completely integrable, four-dimensional symplectic map. In the first study we compute some numerical approximations to Birkhoff periodic orbits; sequences of such orbits should approximate any higher dimensional analogs of the cantori. In the second study we prove converse KAM theorems; that is, we use a combination of analytic arguments and rigorous, machine-assisted computations to find perturbations so large that no KAM tori survive. We are able to show that the last few of our Birkhoff orbits exist in a regime where there are no tori.

Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

Planar reflection of gaseous detonations

Pipes containing flammable gaseous mixtures may be subjected to internal detonation. When the detonation normally impinges on a closed end, a reflected shock wave is created to bring the flow back to rest. This study built on the work of Karnesky (2010) and examined deformation of thin-walled stainless steel tubes subjected to internal reflected gaseous detonations. A ripple pattern was observed in the tube wall for certain fill pressures, and a criterion was developed that predicted when the ripple pattern would form. A two-dimensional finite element analysis was performed using Johnson-Cook material properties; the pressure loading created by reflected gaseous detonations was accounted for with a previously developed pressure model. The residual plastic strain between experiments and computations was in good agreement.

During the examination of detonation-driven deformation, discrepancies were discovered in our understanding of reflected gaseous detonation behavior. Previous models did not accurately describe the nature of the reflected shock wave, which motivated further experiments in a detonation tube with optical access. Pressure sensors and schlieren images were used to examine reflected shock behavior, and it was determined that the discrepancies were related to the reaction zone thickness extant behind the detonation front. During these experiments reflected shock bifurcation did not appear to occur, but the unfocused visualization system made certainty impossible. This prompted construction of a focused schlieren system that investigated possible shock wave-boundary layer interaction, and heat-flux gauges analyzed the boundary layer behind the detonation front. Using these data with an analytical boundary layer solution, it was determined that the strong thermal boundary layer present behind the detonation front inhibits the development of reflected shock wave bifurcation.

Vibrational pooling and constrained equilibration on surfaces

In this thesis, we provide a statistical theory for the vibrational pooling and fluorescence time dependence observed in infrared laser excitation of CO on an NaCl surface. The pooling is seen in experiment and in computer simulations. In the theory, we assume a rapid equilibration of the quanta in the substrate and minimize the free energy subject to the constraint at any time t of a fixed number of vibrational quanta N(t). At low incident intensity, the distribution is limited to one- quantum exchanges with the solid and so the Debye frequency of the solid plays a key role in limiting the range of this one-quantum domain. The resulting inverted vibrational equilibrium population depends only on fundamental parameters of the oscillator (ω_e and ω_eχ_e) and the surface (ω_D and T). Possible applications and relation to the Treanor gas phase treatment are discussed. Unlike the solid phase system, the gas phase system has no Debye-constraining maximum. We discuss the possible distributions for arbitrary N-conserving diatom-surface pairs, and include application to H:Si(111) as an example.

Computations are presented to describe and analyze the high levels of infrared laser-induced vibrational excitation of a monolayer of absorbed ¹³CO on a NaCl(100) surface. The calculations confirm that, for situations where the Debye frequency limited n domain restriction approximately holds, the vibrational state population deviates from a Boltzmann population linearly in n. Nonetheless, the full kinetic calculation is necessary to capture the result in detail.

We discuss the one-to-one relationship between N and γ and the examine the state space of the new distribution function for varied γ. We derive the Free Energy, F = NγkT − kTln(∑P_n), and effective chemical potential, μn ≈ γkT, for the vibrational pool. We also find the anti correlation of neighbor vibrations leads to an emergent correlation that appears to extend further than nearest neighbor.

Adsorption of Pb(II) and Cu(II) on α-quartz from aqueous solutions: influence of pH, ionic strength, and complexing ligands

Adsorption of aqueous Pb(II) and Cu(II) on α-quartz was studied as a function of time, system surface area, and chemical speciation. Experimental systems contained sodium as a major cation, hydroxide, carbonate, and chloride as major anions, and covered the pH range 4 to 8. In some cases citrate and EDTA were added as representative organic complexing agents. The adsorption equilibria were reached quickly, regardless of the system surface area. The positions of the adsorption equilibria were found to be strongly dependent on pH, ionic strength and concentration of citrate and EDTA. The addition of these non-adsorbing ligands resulted in a competition between chelation and adsorption. The experimental work also included the examination of the adsorption behavior of the doubly charged major cations Ca(II) and Mg(II) as a function of pH.

The theoretical description of the experimental systems was obtained by means of chemical equilibrium-plus-adsorption computations using two adsorption models: one mainly electrostatic (the James-Healy Model), and the other mainly chemical (the Ion Exchange-Surface Complex Formation Model). Comparisons were made between these two models.

The main difficulty in the theoretical predictions of the adsorption behavior of Cu(II) was the lack of the reliable data for the second hydrolysis constant(*β_2) The choice of the constant was made on the basis of potentiometric titratlons of Cu^(2+)

The experimental data obtained and the resulting theoretical observations were applied in models of the chemical behavior of trace metals in fresh oxic waters, with emphasis on Pb(II) and Cu(II).

Boundary-layer transition on a slender cone in hypervelocity flow with real gas effects

The laminar to turbulent transition process in boundary layer flows in thermochemical nonequilibrium at high enthalpy is measured and characterized. Experiments are performed in the T5 Hypervelocity Reflected Shock Tunnel at Caltech, using a 1 m length 5-degree half angle axisymmetric cone instrumented with 80 fast-response annular thermocouples, complemented by boundary layer stability computations using the STABL software suite. A new mixing tank is added to the shock tube fill apparatus for premixed freestream gas experiments, and a new cleaning procedure results in more consistent transition measurements. Transition location is nondimensionalized using a scaling with the boundary layer thickness, which is correlated with the acoustic properties of the boundary layer, and compared with parabolized stability equation (PSE) analysis. In these nondimensionalized terms, transition delay with increasing CO₂ concentration is observed: tests in 100% and 50% CO₂, by mass, transition up to 25% and 15% later, respectively, than air experiments. These results are consistent with previous work indicating that CO₂ molecules at elevated temperatures absorb acoustic instabilities in the MHz range, which is the expected frequency of the Mack second-mode instability at these conditions, and also consistent with predictions from PSE analysis. A strong unit Reynolds number effect is observed, which is believed to arise from tunnel noise. N_Tr for air from 5.4 to 13.2 is computed, substantially higher than previously reported for noisy facilities. Time- and spatially-resolved heat transfer traces are used to track the propagation of turbulent spots, and convection rates at 90%, 76%, and 63% of the boundary layer edge velocity, respectively, are observed for the leading edge, centroid, and trailing edge of the spots. A model constructed with these spot propagation parameters is used to infer spot generation rates from measured transition onset to completion distance. Finally, a novel method to control transition location with boundary layer gas injection is investigated. An appropriate porous-metal injector section for the cone is designed and fabricated, and the efficacy of injected CO₂ for delaying transition is gauged at various mass flow rates, and compared with both no injection and chemically inert argon injection cases. While CO₂ injection seems to delay transition, and argon injection seems to promote it, the experimental results are inconclusive and matching computations do not predict a reduction in N factor from any CO₂ injection condition computed.

Studies of response to earthquake ground motion

A study is made of the accuracy of electronic digital computer calculations of ground displacement and response spectra from strong-motion earthquake accelerograms. This involves an investigation of methods of the preparatory reduction of accelerograms into a form useful for the digital computation and of the accuracy of subsequent digital calculations. Various checks are made for both the ground displacement and response spectra results, and it is concluded that the main errors are those involved in digitizing the original record. Differences resulting from various investigators digitizing the same experimental record may become as large as 100% of the maximum computed ground displacements. The spread of the results of ground displacement calculations is greater than that of the response spectra calculations. Standardized methods of adjustment and calculation are recommended, to minimize such errors.

Studies are made of the spread of response spectral values about their mean. The distribution is investigated experimentally by Monte Carlo techniques using an electric analog system with white noise excitation, and histograms are presented indicating the dependence of the distribution on the damping and period of the structure. Approximate distributions are obtained analytically by confirming and extending existing results with accurate digital computer calculations. A comparison of the experimental and analytical approaches indicates good agreement for low damping values where the approximations are valid. A family of distribution curves to be used in conjunction with existing average spectra is presented. The combination of analog and digital computations used with Monte Carlo techniques is a promising approach to the statistical problems of earthquake engineering.

Methods of analysis of very small earthquake ground motion records obtained simultaneously at different sites are discussed. The advantages of Fourier spectrum analysis for certain types of studies and methods of calculation of Fourier spectra are presented. The digitizing and analysis of several earthquake records is described and checks are made of the dependence of results on digitizing procedure, earthquake duration and integration step length. Possible dangers of a direct ratio comparison of Fourier spectra curves are pointed out and the necessity for some type of smoothing procedure before comparison is established. A standard method of analysis for the study of comparative ground motion at different sites is recommended.