The hybrid extended Born approximation and CG-FFT method forelectromagnetic induction problems

The authors propose the hybridization of the extended Born approximation (EBA) with the conjugate-gradient fast Fourier transform (CG-FFT) method to improve the efficiency of numerical solution of electromagnetic induction problems. This combination improves the solution efficiency in two ways. First, using the FFT in the extended Born approximation decreases the computational cost of the conventional EBA method from O(N²) to O(N log₂ N) arithmetic operations, where N is the number of unknowns in the problem. This approach, referred to as the FFT-EBA method, applies to problems with a fairly large contrast. Secondly, using the EBA as a partial preconditioner for the CG-FFT method increases the convergence speed of the conventional CG-FFT method. This second approach, referred to as the EBA-CGFFT method, is in principle applicable to all problems with a homogeneous background, but is particularly efficient for problems with a higher contrast. Numerical experiments suggest that the combination of these two methods is more accurate and more efficient for electromagnetic induction problems     

Inversion of induction tool measurements using the distorted Borniterative method and CG-FFHT

The inversion of induction tool measurements using the distorted Born iterative method (DBIM) and the conjugate gradient-fast Fourier-Hankel transform (CG-FFHT) is described. The inverse problem is formulated in terms of an integral equation of scattering where the unknown to be sought is the conductivity in the rock formation, when the measurements along a borehole axis are performed. The nonlinear problem is linearized at each stage using the distorted Born approximation. The inhomogeneous medium Green's function in the distorted Born approximation is found by solving a volume integral equation using the CG-FFHT method, which allows a rapid solution to a large problem with reduced computational complexity and memory requirement. In this manner, the inverse problem is solved with a computational complexity proportional to N_tlN log N where N_tl is the number of transmitter locations used in the data collection and N is the total number of pixels used to model the unknown formation. The memory requirement is of order NN_tl     

Efficient Numerical Simulation of Axisymmetric Electromagnetic Induction Measurements Using a High-Order Generalized Extended Born Approximation

This paper develops a high-order generalized extended Born approximation (Ho-GEBA) for the numerical simulation of electromagnetic scattering due to rock formations that exhibit axial symmetry around a wellbore. The resulting equations of Ho-GEBA are solved with a numerical procedure that is as efficient as the extended Born approximation (EBA). With the acceleration of a fast Fourier transform, the operation count is proportional to$O(CN)$, where$N$is the total number of spatial discretization cells and$Cll N$is a constant that depends on the number of discretization cells in the radial direction. Ho-GEBA remains accurate in the near-source scattering region and accounts for multiple scattering in the presence of large conductivity contrasts and relatively large frequencies. Numerical exercises conclusively indicate that the accuracy of Ho-GEBA is superior to that of EBA and the first-order Born approximation while maintaining the same level of algorithmic efficiency. These exercises are carried out on a variety of source–receiver configurations and frequencies typical of single-well borehole induction measurements.     

High-order generalized extended Born approximation for electromagnetic scattering

Previous work on the subject of electromagnetic scattering has shown that the extended Born approximation (EBA) is more accurate than the first-order Born approximation with approximately the same operation count. However, the accuracy of the EBA degrades in cases when the source is very close to the scatterer, or when the electric field exhibits significant spatial variations within the scatterer. This paper introduces a generalized extended Born approximation (GEBA) and its high-order variants (Ho-GEBA) to efficiently and accurately simulate electromagnetic scattering problems. We make use of a generalized series expansion of the internal electric field to construct high-order terms of the generalized extended Born approximation (Ho-GEBA). A salient feature of the Ho-GEBA is its enhanced accuracy over the Born approximation and the EBA, even when only the first-order term of the series expansion is considered in the approximation. This behavior is not conditioned by either the source location or the spatial distribution of the internal electric field. A unique feature of the Ho-GEBA is that it can be used to simulate electromagnetic scattering due to electrically anisotropic media. Such a feature is not possible with approximations of the internal electric field that are based on the behavior of the background electric field. Three-dimensional (3-D) models of electromagnetic scattering are used to benchmark the efficiency and accuracy of the Ho-GEBA, including comparisons against the first-order Born approximation and the EBA.     

Application of successive approximation method to the computationof the Green's function in axisymmetric inhomogeneous media

The successive approximation method (SAM) is applied to the computation of the Green's function in axisymmetric inhomogeneous media, SAM is implemented by using an iterative procedure that produces a series, and the series is proven to be a Taylor series. The condition of the convergence is derived from the theory of functions of several complex variables. In each iteration, the Fourier-Hankel transform and its inverse are applied to the approximation of some order of the Green's function and the result is the approximation one order higher than the original. Fast Fourier-Hankel transform (FFHT) is employed to speed up the computation, and thereby, an algorithm SAM-FFHT is formulated     

Cylindrical FDTD Analysis of LWD Tools Through Anisotropic Dipping-Layered Earth Media

Electrical logging-while-drilling (LWD) tools are commonly used in oil and gas exploration to estimate the conductivity (resistivity) of adjacent Earth media. In general, Earth media exhibit anisotropic conductivities. This implies that when LWD tools are used for deviated and horizontal drilling, the resulting borehole problem may include dipping-layered media with dipping beds having full 3 times 3 conductivity tensors. To model this problem, we describe a 3-D cylindrical finite-difference time-domain (FDTD) algorithm extended to fully anisotropic conductive media and implemented with cylindrical perfectly matched layers to mimic open-domain problems. The 3-D FDTD algorithm is validated against analytical results in simple formations, showing good agreement, and used to simulate the response of LWD tools through anisotropic dipping beds for various values of anisotropic conductivities and dipping angles     

A new correction to the Born approximation

A correction to the Born approximation for the apparent conductivity (induced voltage) in a layered medium is derived. The correction involves a single constant a and is nonlinear in conductivity. An algorithm for choosing a for induction logging applications is derived. The correction is shown to be significantly more accurate than the uncorrected Born approximation at high conductivity contrasts between adjacent beds. The correction does not significantly increase the computation time or complexity of the Born approximation. Thus, it has application to the related inverse problem where the speed of computation of the forward problem is important. In typical cases studied, the correction is shown to reduce the root mean square (RMS) error of the Born approximation to no more than 5% in regions where the Born approximation without correction has a RMS error of up to 30%     

Microwave Subsurface Imaging Using Direct Finite-Difference Frequency-Domain-Based Inversion

We have developed a new algorithm for electromagnetic inverse scattering problems in inhomogeneous media using finite-difference frequency-domain (FDFD) forward modeling, referred to as the FDFD-based inversion method. The key issue of this method is to build a linear expression for the inverse problem from an FDFD forward model by using Born approximation to neglect mutual coupling between scattered pixels and to then solve for the inverse coefficient matrix. An important advantage of this matrix-based method is that there is no need to specify a Green's function. As such, this inverse scattering algorithm is easily implemented and is robust to the heterogeneity in the background. We test the algorithm with a microwave subsurface object detection application using cross-well radar. The new method is compared with conventional inversion using Green's function-based Born approximation. Numerical experiments are presented for a 2-D borehole geometry for buried object detection in uniform soil and in multilayered soil backgrounds.      

用于非均匀介质重建的选代算法收敛性的研究

研究轴对称二维非均匀介质重建迭代算法的收敛性问题。首先借助于玻恩近似将非线性积分方程线性化，然后，利用玻恩迭代法和变形玻恩迭代法，由散射场数据对轴对称二维非均匀介质进行重建。通过几个例子研究了影响迭代算法收敛性的几种因素，如送代算法本身、积分离散化后的网格划分、正则化方法中的正则化参数选取等。     

Radar-diffraction tomography using the modified quasi-linearapproximation

The authors propose a new approach for solving the scattering problem for tomographic imaging based on the modified quasi-linear approximation (MQLA). Rather than using the incident field to approximate the total field inside the scatterer as the Born approximation (BA) does, the authors utilize the incident field plus a secondary field that equals the incident field multiplied by a scattering coefficient, which is referred to as the quasi-linear approximation (QLA). Generally, this coefficient is source dependent and hence, this approximation cannot be used to solve mutiple-source problems. By invoking the localized approximation, they derive a source-independent scattering coefficient and then obtain the modified quasi-linear approximation (MQLA). Based on this approximation, they developed a new diffraction-tomography algorithm and applied it to crosshole radar tomography. This approach is rapid, since iteration techniques are not involved in the algorithm. Numerical simulations indicate that this tomography algorithm can reconstruct images with better imaging quality than the conventional BA algorithm     

Conformal method to eliminate the ADI-FDTD staircasing errors

The alternating-direction-implicit finite-difference time-domain (ADI-FDTD) method is an unconditionally stable method and allows the time step to be increased beyond the Courant-Friedrich-Levy (CFL) stability condition. This method is potentially very useful for modeling electrically small but complex features often encountered in applications. As the regular FDTD method, however, the spatial discretization in the ADI-FDTD method is only first-order accurate for discontinuous media; several researchers have shown that the errors can be very high when the regular ADI-FDTD method is applied to such discontinuous media. On the other hand, the conformal FDTD method has recently emerged as an efficient FDTD method with higher order accuracy. In this work, a second-order accurate ADI-FDTD method using the conformal approximation of spatial derivatives is proposed. This new scheme, called the ADI-CFDTD method, retains the second-order accuracy in both temporal and spatial discretizations even for discontinuous media with metallic structures, and is unconditionally stable. 2D and 3D examples demonstrate the efficacy of this method and its application in EMC problems.     

Fast numerical modeling of multitransmitter electromagnetic data using multigrid quasi-linear approximation

Multitransmitter electromagnetic (EM) surveys are widely used in remote-sensing and geophysical exploration. The interpretation of the multitransmitter geophysical data requires numerous three-dimensional (3-D) modelings of the responses of the receivers for different geoelectrical models of complex geological formations. In this paper, we introduce a fast method for 3-D modeling of EM data, based on a modified version of quasilinear approximation, which uses a multigrid approach. This method significantly speeds up the modeling of multitransmitter-multireceiver surveys. The developed algorithm has been applied for the interpretation of marine controlled-source electromagnetic (MCSEM) data. We have tested our new method using synthetic problems and for the simulation of MCSEM data for a geoelectrical model of a Gemini salt body.     

Quasi-maximum-likelihood multiuser detection using semi-definiterelaxation with application to synchronous CDMA

The maximum-likelihood (ML) multiuser detector is well known to exhibit better bit-error-rate (BER) performance than many other multiuser detectors. Unfortunately, ML detection (MLD) is a nondeterministic polynomial-time hard (NP-hard) problem, for which there is no known algorithm that can find the optimal solution with polynomial-time complexity (in the number of users). A polynomial-time approximation method called semi-definite (SD) relaxation is applied to the MLD problem with antipodal data transmission. SD relaxation is an accurate approximation method for certain NP-hard problems. The SD relaxation ML (SDR-ML) detector is efficient in that its complexity is of the order of K^3.5, where K is the number of users. We illustrate the potential of the SDR-ML detector by showing that some existing detectors, such as the decorrelator and the linear-minimum-mean-square-error detector, can be interpreted as degenerate forms of the SDR-ML detector. Simulation results indicate that the BER performance of the SDR-ML detector is better than that of these existing detectors and is close to that of the true ML detector, even when the cross-correlations between users are strong or the near-far effect is significant     

The Nehari shuffle: FIR(q) filter design with guaranteederror bounds

An approach to the problem of designing a finite impulse response filter of specified length q which approximates in uniform frequency (L_∞) norm a given desired (possibly infinite impulse response) causal, stable filter transfer function is presented. An algorithm-independent lower bound on the achievable approximation error is derived, and an approximation method that involves the solution of a fixed number of all-pass (Nehari) extension problems (and is therefore called the Nehari shuffle) is presented. Upper and lower bounds on the approximation error are derived for the algorithm. Examples indicate that the method closely approaches the derived global lower bound. The method is compared with the Preuss (complex Remez exchange) algorithm in some examples     

An algorithm for determination of the amplitudes of reflected and transmitted waves in the case when counterpropagating waves are incident on a multilayer stepwise inhomogeneous structure

A simple algorithm is proposed for derivimg analytical expressions for the amplitudes of reflected and transmitted waves in the case when two 1D counterpropagating waves are incident on a multilayer stepwise inhomogeneous structure. Wave amplitudes are analytically expressed for structures consisting of three, four, and five layers. The proposed algorithm is applied to solve numerically the problem of wave propagation in an inhomogeneous structure where the wave number linearly changes along the structure’s length. The algorithm involves approximation of a smooth inhomogeneity by a step one. A criterion and conditions are obtained for the applicability of the step approximation for the investigation of wave propagation through inhomogeneous media with smoothly varying parameters. It is shown that the algorithm can be applied to problems on propagation of electromagnetic waves in the cases of the normal and oblique incidence.     

Constructing free-energy approximations and generalized belief propagation algorithms

Important inference problems in statistical physics, computer vision, error-correcting coding theory, and artificial intelligence can all be reformulated as the computation of marginal probabilities on factor graphs. The belief propagation (BP) algorithm is an efficient way to solve these problems that is exact when the factor graph is a tree, but only approximate when the factor graph has cycles. We show that BP fixed points correspond to the stationary points of the Bethe approximation of the free energy for a factor graph. We explain how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms. We emphasize the conditions a free energy approximation must satisfy in order to be a "valid" or "maxent-normal" approximation. We describe the relationship between four different methods that can be used to generate valid approximations: the "Bethe method", the "junction graph method", the "cluster variation method", and the "region graph method". Finally, we explain how to tell whether a region-based approximation, and its corresponding GBP algorithm, is likely to be accurate, and describe empirical results showing that GBP can significantly outperform BP.     

基于双层ACA算法快速求解单站RCS问题

利用积分方程法计算三维目标单站RCS时,需要逐个角度地进行矩阵方程的求解。为了提高计算效率,本文采用自适应交叉近似算法(ACA)对多角度照射时生成的激励矩阵进行低秩压缩,减少了矩阵方程的求解次数;进一步基于单站角度上的分组方式提出了双层ACA算法,该算法对内存占用极小,提高了算法的并行性,而且更有效地实现了激励矩阵的降秩;最后结合多层快速多极子算法(MLFMA)实现电大尺寸目标的快速求解。数值计算结果表明,该算法能大幅减少大宽角条件下的单站RCS计算时间,具有较高的计算精度和计算效率。     

DPBD—设计一类强NP—Complete问题近似算法的有效方法

本文针对一类强NP-Complete问题近似算法的设计问题,提出一种通用的设计策略DPBD,它通过一局部近似算法而获得一全局近似算法,并保证精度在一定范围内.最后,本文将DPBD应用于一著名的NP难度问题:平面Covering问题,对方法的有效性给予了证实.     

3-D numerical mode-matching (NMM) method for resistivitywell-logging tools

A three-dimensional (3-D) numerical mode-matching (NMM) method is presented for Poisson's equation in general inhomogeneons media. It reduces the original 3-D problem into a series of two-dimensional (2-D) eigenvalue problems plus a one-dimensional (1-D) layered medium problem, which can be modeled efficiently by a recursion procedure. The algorithm is tested for several 3-D inhomogeneous media and an excellent agreement between the NMM and analytical solutions is obtained for all test cases. We demonstrate some typical applications of the 3-D NMM algorithm in resistivity well logging, including invasion zones of noncircular shape, vertical and horizontal fractures, and horizontal wells. The solution procedure proposed is directly applicable to wave propagation in 3-D inhomogeneous media     

基于凸优化方法的认知雷达波形设计

针对认知雷达扩展目标检测的问题,提出了一种与目标散射特性相关的相位编码信号设计方法,利用半正定松弛将输出信噪比的优化问题松弛为一个凸优化问题,并利用一维交互迭代搜索逼近原问题的全局最优解。该方法具有收敛速度块、运算量小等优点,能够准确逼近全局最优解。