Search for: All records

Starting from Kirchhoff-Huygens representation and Duhamel's principle of time-domain wave equations, we propose novel butterfly-compressed Hadamard integrators for self-adjoint wave equations in both time and frequency domain in an inhomogeneous medium. First, we incorporate the leading term of Hadamard's ansatz into the Kirchhoff-Huygens representation to develop a short-time valid propagator. Second, using Fourier transform in time, we derive the corresponding Eulerian short-time propagator in the frequency domain; on top of this propagator, we further develop a time-frequency-time (TFT) method for the Cauchy problem of time-domain wave equations. Third, we further propose a time-frequency-time-frequency (TFTF) method for the corresponding point-source Helmholtz equation, which provides Green's functions of the Helmholtz equation for all angular frequencies within a given frequency band. Fourth, to implement the TFT and TFTF methods efficiently, we introduce butterfly algorithms to compress oscillatory integral kernels at different frequencies. As a result, the proposed methods can construct wave field beyond caustics implicitly and advance spatially overturning waves in time naturally with quasi-optimal computational complexity and memory usage. Furthermore, once constructed the Hadamard integrators can be employed to solve both time-domain wave equations with various initial conditions and frequency-domain wave equations with different point sources. Numerical examples for two-dimensional wave equations illustrate the accuracy and efficiency of the proposed methods. 

We have developed a Liouville partial-differential-equation (PDE)-based method for computing complex-valued eikonals in real phase space in the multivalued sense in attenuating media with frequency-independent qualify factors, where the new method computes the real and imaginary parts of the complex-valued eikonal in two steps by solving Liouville equations in real phase space. Because the earth is composed of attenuating materials, seismic waves usually attenuate so that seismic data processing calls for properly treating the resulting energy losses and phase distortions of wave propagation. In the regime of high-frequency asymptotics, the complex-valued eikonal is one essential ingredient for describing wave propagation in attenuating media because this unique quantity summarizes two wave properties into one function: Its real part describes the wave kinematics and its imaginary part captures the effects of phase dispersion and amplitude attenuation. Because some popular ordinary-differential-equation (ODE)-based ray-tracing methods for computing complex-valued eikonals in real space distribute the eikonal function irregularly in real space, we are motivated to develop PDE-based Eulerian methods for computing such complex-valued eikonals in real space on regular meshes. Therefore, we solved novel paraxial Liouville PDEs in real phase space so that we can compute the real and imaginary parts of the complex-valued eikonal in the multivalued sense on regular meshes. We call the resulting method the Liouville PDE method for complex-valued multivalued eikonals in attenuating media; moreover, this new method provides a unified framework for Eulerianizing several popular approximate real-space ray-tracing methods for complex-valued eikonals, such as viscoacoustic ray tracing, real viscoelastic ray tracing, and real elastic ray tracing. In addition, we also provide Liouville PDE formulations for computing multivalued ray amplitudes in a weakly viscoacoustic medium. Numerical examples, including a synthetic gas-cloud model, demonstrate that our methods yield highly accurate complex-valued eikonals in the multivalued sense. 

High-resolution reconstruction of spatial chromosome organizations from chromatin contact maps is highly demanded, but is hindered by extensive pairwise constraints, substantial missing data, and limited resolution and cell-type availabilities. Here, we present FLAMINGO, a computational method that addresses these challenges by compressing inter-dependent Hi-C interactions to delineate the underlying low-rank structures in 3D space, based on the low-rank matrix completion technique. FLAMINGO successfully generates 5 kb- and 1 kb-resolution spatial conformations for all chromosomes in the human genome across multiple cell-types, the largest resources to date. Compared to other methods using various experimental metrics, FLAMINGO consistently demonstrates superior accuracy in recapitulating observed structures with raises in scalability by orders of magnitude. The reconstructed 3D structures efficiently facilitate discoveries of higher-order multi-way interactions, imply biological interpretations of long-range QTLs, reveal geometrical properties of chromatin, and provide high-resolution references to understand structural variabilities. Importantly, FLAMINGO achieves robust predictions against high rates of missing data and significantly boosts 3D structure resolutions. Moreover, FLAMINGO shows vigorous cross cell-type structure predictions that capture cell-type specific spatial configurations via integration of 1D epigenomic signals. FLAMINGO can be widely applied to large-scale chromatin contact maps and expand high-resolution spatial genome conformations for diverse cell-types.