Low-rank optimization on the cone of positive semidefinite matrices

We propose an algorithm for solving optimization problems defined on a subset of the cone of symmetric positive semidefinite matrices. This algorithm relies on the factorization X = Y Y T , where the number of columns of Y fixes an upper bound on the rank of the positive semidefinite matrix X. It is thus very effective for solving problems that have a low-rank solution. The factorization X = Y Y T leads to a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second-order optimization method with guaranteed quadratic convergence. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. In contrast to existing methods, the proposed algorithm converges monotonically to the sought solution. Its numerical efficiency is evaluated on two applications: the maximal cut of a graph and the problem of sparse principal component analysis. © 2010 Society for Industrial and Applied Mathematics.

复杂介质中地震波场数值模拟研究——基于广义正交多项式迭积微分算子法

In this paper, we propose a new numerical modeling method – Convolutional Forsyte Polynomial Differentiator (CFPD), aimed at simulating seismic wave propagation in complex media with high efficiency and accuracy individually owned by short-scheme finite differentiator and general convolutional polynomial method. By adjusting the operator length and optimizing the operator coefficient, both global and local informations can be easily incorporated into the wavefield which is important to invert the undersurface geological structure. The key issue in this paper is to introduce the convolutional differentiator based on Forsyte generalized orthogonal polynomial in mathematics into the spatial differentiation of the first velocity-stress equation. To match the high accuracy of the spatial differentiator, this method in the time coordinate adopts staggered grid finite difference instead of conventional finite difference to model seismic wave propagation in heterogeneous media. To attenuate the reflection artifacts caused by artificial boundary, Perfectly Matched Layer (PML) absorbing boundary is also being considered in the method to deal with boundary problem due to its advantage of automatically handling large-angle emission. The PML formula for acoustic equation and first-order velocity-stress equation are also derived in this paper. There is little difference to implement the PML boundary condition in all kind of wave equations, but in Biot media, special attenuation factors should be taken. Numerical results demonstrate that the PML boundary condition is better than Cerjan absorbing boundary condition which makes it more suitable to hand the artificial boundary reflection. Based on the theories of anisotropy, Biot two-phase media and viscous-elasticity, this paper constructs the constitutive relationship for viscous-elastic and two-phase media, and further derives the first-order velocity-stress equation for 3D viscous-elastic and two-phase media. Numerical modeling using CFPD method is carried out in the above-mentioned media. The results modeled in the viscous-elastic media and the anisotropic pore elastic media can better explain wave phenomena of the true earth media, and can also prove that CFPD is a useful numerical tool to study the wave propagation in complex media.

粘弹性介质中的地震波传播与波形反演研究

The real earth is far away from an ideal elastic ball. The movement of structures or fluid and scattering of thin-layer would inevitably affect seismic wave propagation, which is demonstrated mainly as energy nongeometrical attenuation. Today, most of theoretical researches and applications take the assumption that all media studied are fully elastic. Ignoring the viscoelastic property would, in some circumstances, lead to amplitude and phase distortion, which will indirectly affect extraction of traveltime and waveform we use in imaging and inversion. In order to investigate the response of seismic wave propagation and improve the imaging and inversion quality in complex media, we need not only consider into attenuation of the real media but also implement it by means of efficient numerical methods and imaging techniques. As for numerical modeling, most widely used methods, such as finite difference, finite element and pseudospectral algorithms, have difficulty in dealing with problem of simultaneously improving accuracy and efficiency in computation. To partially overcome this difficulty, this paper devises a matrix differentiator method and an optimal convolutional differentiator method based on staggered-grid Fourier pseudospectral differentiation, and a staggered-grid optimal Shannon singular kernel convolutional differentiator by function distribution theory, which then are used to study seismic wave propagation in viscoelastic media. Results through comparisons and accuracy analysis demonstrate that optimal convolutional differentiator methods can solve well the incompatibility between accuracy and efficiency, and are almost twice more accurate than the same-length finite difference. They can efficiently reduce dispersion and provide high-precision waveform data. On the basis of frequency-domain wavefield modeling, we discuss how to directly solve linear equations and point out that when compared to the time-domain methods, frequency-domain methods would be more convenient to handle the multi-source problem and be much easier to incorporate medium attenuation. We also prove the equivalence of the time- and frequency-domain methods by using numerical tests when assumptions with non-relaxation modulus and quality factor are made, and analyze the reason that causes waveform difference. In frequency-domain waveform inversion, experiments have been conducted with transmission, crosshole and reflection data. By using the relation between media scales and characteristic frequencies, we analyze the capacity of the frequency-domain sequential inversion method in anti-noising and dealing with non-uniqueness of nonlinear optimization. In crosshole experiments, we find the main sources of inversion error and figure out how incorrect quality factor would affect inverted results. When dealing with surface reflection data, several frequencies have been chosen with optimal frequency selection strategy, with which we use to carry out sequential and simultaneous inversions to verify how important low frequency data are to the inverted results and the functionality of simultaneous inversion in anti-noising. Finally, I come with some conclusions about the whole work I have done in this dissertation and discuss detailly the existing and would-be problems in it. I also point out the possible directions and theories we should go and deepen, which, to some extent, would provide a helpful reference to researchers who are interested in seismic wave propagation and imaging in complex media.

三维油藏数值模拟正反演算法研究

The dynamic prediction of complex reservoir development is one of the important research contents of dynamic analysis of oil and gas development. With the increase development of time, the permeabilities and porosities of reservoirs and the permeability of block reservoir at its boundaries are dynamically changing. How to track the dynamic change of permeability and porosity and make certain the permeability of block reservoir at its boundary is an important practical problem. To study developing dynamic prediction of complex reservoir, the key problem of research of dynamic prediction of complex reservoir development is realizing inversion of permeability and porosity. To realize the inversion, first of all, the fast forward and inverse method of 3-dimension reservoir simulation must be studied. Although the inversion has been widely applied to exploration and logging, it has not been applied to3-dimension reservoir simulation. Therefore, the study of fast forward and inverse method of 3-dimension reservoir simulation is a cutting-edge problem, takes on important realistic signification and application value. In this dissertation, 2-dimension and 3-dimension fluid equations in porous media are discretized by finite difference, obtaining finite difference equations to meet the inner boundary conditions by Peaceman's equations, giving successive over relaxation iteration of 3-dimension fluid equations in porous media and the dimensional analysis. Several equation-solving methods are compared in common use, analyzing its convergence and convergence rate. The alternating direction implicit procedure of 2-dimension has been turned into successive over relaxation iteration of alternating direction implicit procedure of 3-dimension fluid equations in porous media, which possesses the virtues of fast computing speed, needing small memory of computer, good adaptability for heterogeneous media and fast convergence rate. The geological model of channel-sandy reservoir has been generated with the help of stochastic simulation technique, whose cross sections of channel-sandy reservoir are parabolic shapes. This method makes the hard data commendably meet, very suit for geological modeling of containing complex boundary surface reservoir. To verify reliability of the method, theoretical solution and numerical solution are compared by simplifying model of 3-dimension fluid equations in porous media, whose results show that the only difference of the two pressure curves is that the numerical solution is lower than theoretical at the wellbore in the same space. It proves that using finite difference to solve fluid equations in porous media is reliable. As numerical examples of 3-dimension heterogeneous reservoir of the single-well and multi-well, the pressure distributions have been computed respectively, which show the pressure distributions there are clearly difference as difference of the permeabilities is greater than one order of magnitude, otherwise there are no clearly difference. As application, the pressure distribution of the channel-sandy reservoir have been computed, which indicates that the space distribution of pressure strongly relies on the direction of permeability, and is sensitive for space distributions of permeability. In this dissertation, the Peaceman's equations have been modified into solving vertical well problem and horizontal well problem simultaneously. In porous media, a 3D layer reservoir in which contain vertical wells and horizontal wells has been calculated with iteration. For channel-sandy reservoir in which there are also vertical wells and horizontal wells, a 3D transient heterogeneous fluid equation has been discretized. As an example, the space distribution of pressure has been calculated with iteration. The results of examples are accord with the fact, which shows the modification of Peaceman's equation is correct. The problem has been solved in the space where there are vertical and horizontal wells. In the dissertation, the nonuniform grid permeability integration equation upscaling method, the nonuniform grid 2D flow rate upscaling method and the nonuniform grid 3D flow rate upscaling method have been studied respectively. In those methods, they enhance computing speed greatly, but the computing speed of 3D flow rate upscaling method is faster than that of 2D flow rate upscaling method, and the precision of 3D flow rate upscaling method is better than that of 2D flow rate upscaling method. The results also show that the solutions of upscaling method are very approximating to that of fine grid blocks. In this paper, 4 methods of fast adaptive nonuniform grid upscaling method of 3D fluid equations in porous media have been put forward, and applied to calculate 3D heterogeneous reservoir and channel-sandy reservoir, whose computing results show that the solutions of nonuniform adaptive upscaling method of 3D heterogeneous fluid equations in porous media are very approximating to that of fine grid blocks in the regions the permeability or porosity being abnormity and very approximating to that of coarsen grid blocks in the other region, however, the computing speed of adaptive upscaling method is 100 times faster than that of fine grid block method. The formula of sensitivity coefficients are derived from initial boundary value problems of fluid equations in porous media by Green's reciprocity principle. The sensitivity coefficients of wellbore pressure to permeability parameters are given by Peaceman's equation and calculated by means of numerical calculation method of 3D transient anisotropic fluid equation in porous media and verified by direct method. The computing results are in excellent agreement with those obtained by the direct method, which shows feasibility of the method. In the dissertation, the calculating examples are also given for 3D reservoir, channel-sandy reservoir and 3D multi-well reservoir, whose numerical results indicate: around the well hole, the value of the sensitivity coefficients of permeability is very large, the value of the sensitivity coefficients of porosity is very large too, but the sensitivity coefficients of porosity is much less than the sensitivity coefficients of permeability, so that the effect of the sensitivity coefficients of permeability for inversion of reservoir parameters is much greater than that of the sensitivity coefficients of porosity. Because computing the sensitivity coefficients needs to call twice the program of reservoir simulation in one iteration, realizing inversion of reservoir parameters must be sustained by the fast forward method. Using the sensitivity coefficients of permeability and porosity, conditioned on observed valley erosion thickness in wells (hard data), the inversion of the permeabilities and porosities in the homogeneous reservoir, homogeneous reservoir only along the certain direction and block reservoir are implemented by Gauss-Newton method or conjugate gradient method respectively. The results of our examples are very approximating to the real data of permeability and porosity, but the convergence rate of conjugate gradient method is much faster than that of Gauss-Newton method.

VSP克希霍夫法多波联合成像

Geophones being inside the well, VSP can record upgoing and downgoing P waves, upgoing and downgoing S waves simultaneously.Aiming at overcoming the shortages of the known VSP velocity tomography , attenuation tomography , inverse Q filtering and VSP image method , this article mainly do the following jobs:CD; I do the common-source-point raytracing by soving the raytracing equations with Runge-Kutta method, which can provide traveltime , raypath and amplitude for VSP velocity tomography , attenuation tomography and VSP multiwave migration.(D. The velocity distribution can be inversed from the difference between the computed traveltime and the observed traveltime of the VSP downgoing waves. I put forward two methods: A. VSP building-velocity tomography method that doesn't lie on the layered model from which we can derive the slowness of the grids' crunodes . B. deformable layer tomography method from which we can get the location of the interface if the layer's velocity is known..(3). On the basis of the velocity tomography , using the attenuation information shown by the VSP seismic wave , we can derive the attenuation distribution of the subsurface. I also present an algorithm to solve the inverse Q filtering problem directly and accurately from the Q modeling equation . Numerical results presented have shown that our algorithm gives reliable results . ?. According to the theory that the transformed point is the point where the four kinds of wave come into being , and where the stacked energy will be the largest than at other points . This article presents a VSP multiwave Kirchhoff migration method . Application on synthetic examples and field seismic records have shown that the algorithm gives reliable results . (5). When the location of the interface is determined and the velocity of the P wave and S wave is known , we can obtain the transmittivity and reflection coefficient 5 thereby we can gain the elastic parameters . This method is also put into use derive good result.Above all, application on models and field seismic records show that the method mentioned above is efficient and accurate .

Coherent Behavior from Incoherent Knowledge Sources in the Automatic Synthesis of Numerical Computer Programs

A fundamental problem in artificial intelligence is obtaining coherent behavior in rule-based problem solving systems. A good quantitative measure of coherence is time behavior; a system that never, in retrospect, applied a rule needlessly is certainly coherent; a system suffering from combinatorial blowup is certainly behaving incoherently. This report describes a rule-based problem solving system for automatically writing and improving numerical computer programs from specifications. The specifications are in terms of "constraints" among inputs and outputs. The system has solved program synthesis problems involving systems of equations, determining that methods of successive approximation converge, transforming recursion to iteration, and manipulating power series (using differing organizations, control structures, and argument-passing techniques).

The Dirichlet problem in convex bounded domains for operators with L^\infty-coefficients

M.Hieber, I.Wood: The Dirichlet problem in convex bounded domains for operators with L^\infty-coefficients, Diff. Int. Eq., 20, 7 (2007),721-734.

Singular perturbation of quantum stochastic differential equations with coupling through an oscillator mode

Gough, John; Van Handel, R., (2007) 'Singular perturbation of quantum stochastic differential equations with coupling through an oscillator mode', Journal of Statistical Physics 127(3) pp.575-607 RAE2008

Quantum Flows as Markovian Limit of Emission, Absorption and Scattering Interactions

Gough, John, (2004) 'Quantum Flows as Markovian Limit of Emission, Absorption and Scattering Interactions', Communications in Mathematical Physics 254 pp.498-512 RAE2008

Newton's aerodynamic problem in media of chaotically moving particles

Plakhov, A.Y.; Torres, D., (2005) 'Newton's aerodynamic problem in media of chaotically moving particles', Sbornik: Mathematics 196(6) pp.885-933 RAE2008

The Dirichlet problem in convex bounded domains for operators with L8-coefficients

Wood, Ian; Hieber, M., (2007) 'The Dirichlet problem in convex bounded domains for operators with L8-coefficients', Differential and Integral Equations 20 pp.721-734 RAE2008

Hamilton?Jacobi?Bellman equations for quantum optimal feedback control

Gough, John; Belavkin, V.P.; Smolianov, O.G., (2005) 'Hamilton?Jacobi?Bellman equations for quantum optimal feedback control', Journal of Optics B: Quantum and Semiclassical Optics 7 pp.S237-S244 RAE2008

Asymptotic behaviour of the elastic solution near the tip of a crack situated at a nonideal interface

Mishuris, G; Kuhn, G., (2001) 'Asymptotic behaviour of the elastic solution near the tip of a crack situated at a nonideal interface', Zeitschrift f?r Angewandte Mathematik und Mechanik 81(12) pp.811-826 RAE2008