Solving the Coupled System Improves Computational Efficiency of the Bidomain Equations

The bidomain equations are frequently used to model the propagation of cardiac action potentials across cardiac tissue. At the whole organ level, the size of the computational mesh required makes their solution a significant computational challenge. As the accuracy of the numerical solution cannot be compromised, efficiency of the solution technique is important to ensure that the results of the simulation can be obtained in a reasonable time while still encapsulating the complexities of the system. In an attempt to increase efficiency of the solver, the bidomain equations are often decoupled into one parabolic equation that is computationally very cheap to solve and an elliptic equation that is much more expensive to solve. In this study, the performance of this uncoupled solution method is compared with an alternative strategy in which the bidomain equations are solved as a coupled system. This seems counterintuitive as the alternative method requires the solution of a much larger linear system at each time step. However, in tests on two 3-D rabbit ventricle benchmarks, it is shown that the coupled method is up to 80% faster than the conventional uncoupled method-and that parallel performance is better for the larger coupled problem.     

Reduced-order preconditioning for bidomain simulations

Simulations of the bidomain equations involve solving large, sparse, linear systems of the form Ax = b. Being an initial value problems, it is solved at every time step. Therefore, efficient solvers are essential to keep simulations tractable. Iterative solvers, especially the preconditioned conjugate gradient (PCG) method, are attractive since memory demands are minimized compared to direct methods, albeit at the cost of solution speed. However, a proper preconditioner can drastically speed up the solution process by reducing the number of iterations. In this paper, a novel preconditioner for the PCG method based on system order reduction using the Arnoldi method (A-PCG) is proposed. Large order systems, generated during cardiac bidomain simulations employing a finite element method formulation, are solved with the A-PCG method. Its performance is compared with incomplete LU (ILU) preconditioning. Results indicate that the A-PCG estimates an approximate solution considerably faster than the ILU, often within a single iteration. To reduce the computational demands in terms of memory and run time, the use of a cascaded preconditioner was suggested. The A-PCG was applied to quickly obtain an approximate solution, and subsequently a cheap iterative method such as successive overrelaxation (SOR) is applied to further refine the solution to arrive at a desired accuracy. The memory requirements are less than those of direct LU but more than ILU method. The proposed scheme is shown to yield significant speedups when solving time evolving systems.     

Solving the cardiac bidomain equations for discontinuous conductivities

Fast simulations of cardiac electrical phenomena demand fast matrix solvers for both the elliptic and parabolic parts of the bidomain equations. It is well known that fast matrix solvers for the elliptic part must address multiple physical scales in order to show robust behavior. Recent research on finding the proper solution method for the bidomain equations has addressed this issue whereby multigrid preconditioned conjugate gradients has been used as a solver. In this paper, a more robust multigrid method, called Black Box Multigrid, is presented as an alternative to conventional geometric multigrid, and the effect of discontinuities on solver performance for the elliptic and parabolic part is investigated. Test problems with discontinuities arising from inserted plunge electrodes and naturally occurring myocardial discontinuities are considered. For these problems, we explore the advantages to using a more advanced multigrid method like Black Box Multigrid over conventional geometric multigrid. Results will indicate that for certain discontinuous bidomain problems Black Box Multigrid provides 60% faster simulations than using conventional geometric multigrid. Also, for the problems examined, it will be shown that a direct usage of conventional multigrid leads to faster simulations than an indirect usage of conventional multigrid as a preconditioner unless there are sharp discontinuities.     

一种适合FMM法的预处理技术在车载通信系统中的应用

提出了一种针对适合于快速多极子(FMM)近场作用矩阵的不完全LU预条件方法。与传统单纯靠填充参数来控制非零元素个数的ILU分解方法相比,该方法由于引入了数值丢弃阈值,因而可以获得更好的预条件矩阵。利用该预条件技术,收敛更快,计算花费的时间和存储量更少。数值试验表明,此方法是一种适合FMM计算的预条件技术。     

一种新型针对快速多极子法(FMM)的预条件技术

提出了一种针对FMM近场作用矩阵块的不完全LU预条件方法。和传统单纯依靠填充参数来控制非零元素个数的ILU分解方法相比，该方法由于引入了数值丢弃阈值，因而可获得性能更好的预条件矩阵。利用该项预条件技术，迭代过程变得更健壮，而且收敛也更快，计算花费的时间也更少。数值实验表明：这种基于双丢弃准则的ILUT预条件技术，是一种非常适合FMM计算的预条件处理方法。     

Accurate numerical modeling of the TARA reflector system

The radiation pattern of the large parabolic reflectors of the Transportable Atmospheric RAdar system (TARA), developed at Delft University of Technology, has been accurately simulated. The electric field integral equation (EFIE) formulation has been applied to a model of the reflectors including the feed housing and supporting struts, discretised using the method of moments. Because the problem is electrically large (the reflector has a diameter of 33/spl lambda/) and nonsymmetrical, this lead to a badly conditioned linear system of approximately half a million unknowns. In order to solve this system, an iterative solver (generalized minimum residual method) was used, in combination with the multilevel fast multipole method. Because of the bad conditioning, the system could only be solved by using a huge preconditioner. A new block-incomplete LU preconditioner (ILU) algorithm has been employed to allow for efficient out-of-computer core memory preconditioning.     

基于不完全分解预优共轭梯度法的电源和地线网络求解器

在超大规模集成电路的电源和地线网络的设计中 ,求解由该网络上每个节点的电压和每条边上的电流是最基本的运算 ,它对电源和地线网络拓扑结构设计和线宽优化算法的质量具有直接的影响 .针对电源和地线网络的特殊性 ,提出了一个高效的电源和地线网络求解器 ,包括电路网络中树结构的合并与恢复和用不完全分解的预优共轭梯度法来求解节点电压方程 .该求解器的运算速度很快 ,所耗费的内存很小 ,同时具有很强的鲁棒性     

Nested multigrid vector and scalar potential finite element method for fast computation of two-dimensional electromagnetic scattering

Nested multigrid techniques are combined with the ungauged vector and scalar potential formulation of the finite-element method to accelerate the convergence of the numerical solution of two-dimensional electromagnetic scattering problems. The finite-element modeling is performed on nested meshes of the same computational domain. The conjugate gradient method is used to solve the resultant finite-element matrix for the finest mesh, while the nested multigrid vector and scalar potential algorithm acts as the preconditioner of the iterative solver. Numerical experiments are used to demonstrate the superior numerical convergence and efficient memory usage of the proposed algorithm.     

PC集群系统中MPI并行矩量法研究

针对复杂环境的电磁兼容分析中计算量过大、耗时太长的障碍,该文组建了一个高性能PC集群系统,以 此为硬件平台研究了MPI并行环境下的并行矩量法。论文首先给出了与并行共轭梯度法求解矩阵方程对应的矩量 法矩阵的棋盘块划分方式,然后详细地讨论了并行共轭梯度算法求解矩量法矩阵方程的并行实现。作为应用实例计 算了某飞行器模型的散射特性,并测试了在PC集群系统中本文并行矩量法程序的性能。     

基于紧支撑径向基函数与共轭梯度法的大规模散乱数据快速曲面插值

该文提出一种快速大规模散乱数据的曲面插值算法。在此算法中,首先采用紧支撑径向基函数(CSRBF)作为插值基函数,采用CSRBF的优点是保证构成的系数方程组是对称正定而且系数是稀疏的。这样可保证系数方程组一定可解而且可以减少内存的开销。其次采用共轭梯度法求解大规模系数方程组。该算法在系数方程组的系数矩阵A:NN是对称正定的情况下,最多迭代N步就可以求得方程组的解,实验结果表明该算法的快速性,特别适合大规模散乱数据的曲面的插值。     

An efficient numerical technique for the solution of the monodomain and bidomain equations

Most numerical schemes for solving the monodomain or bidomain equations use a forward approximation to some or all of the time derivatives. This approach, however, constrains the maximum timestep that may be used by stability considerations as well as accuracy considerations. Stability may be ensured by using a backward approximation to all time derivatives, although this approach requires the solution of a very large system of nonlinear equations at each timestep which is computationally prohibitive. In this paper we propose a semi-implicit algorithm that ensures stability. A linear system is solved on each timestep to update the transmembrane potential and, if the bidomain equations are being used, the extracellular potential. The remainder of the equations to be solved uncouple into small systems of ordinary differential equations. The backward Euler method may be used to solve these systems and guarantee numerical stability: as these systems are small, only the solution of small nonlinear systems are required. Simulations are carried out to show that the use of this algorithm allows much larger timesteps to be used with only a minimal loss of accuracy. As a result of using these longer timesteps the computation time may be reduced substantially.     

Analysis of Millimeter Wave Scattering by the Infinite Plane Metallic Grating Using PCG-FFT Technique

In this paper, both fast Fourier transformation (FFT) and preconditioned CG technique are introduced into method of lines (MOL) to further enhance the computational efficiency of this semi-analytic method. Electromagnetic wave scattering by an infinite plane metallic grating is used as the examples to describe its implementation. For arbitrary incident wave, Helmholz equation and boundary condition are first transformed into new ones so that the impedance matrix elements are calculated by FFT technique. As a result, this Topelitz impedance matrix only requires O(N) memory storage for the conjugate gradient FFT method to solve the current distribution with the computational complexity O(N log N) . Our numerical results show that circulate matrix preconditioner can speed up CG-FFT method to converge in much smaller CPU time than the banded matrix preconditioner.     

预条件共轭梯度法在辐射和散射问题中的应用

用矩量法求解一些辐射和散射问题 ,如线天线辐射和线状体散射等问题时 ,可以产生一个 Toeplitz线性方程组 ,采用预条件共轭梯度法 (PCG)与快速富里叶变换 (FFT)的结合方法 (PCGFFT)来求解该方程组 ,其中预条件器采用 T.Chan的优化循环预条件器。使用 PCGFFT算法 ,可有效地节省内存 ,提高了计算速度。为说明其有效性 ,将 PCGFFT算法与 CGFFT算法以及 Levinson递推算法进行了对比。     

用MoM—PCG—FFT分析金属栅有限阵列的散射问题

本文用矩量法、预条件共轭梯度法和快速傅里叶变换（MoM-PCG-FFT)的混合技术来分析金属栅有限阵列的电磁散射问题。首先以等效电流作为未知函数建立积分方程组或积分－微分方程组,再用矩量法（脉冲／点匹配）获得一个线性代数方程组,其系数矩阵是一个对称二重复Toeplitz矩阵,基于这一特点,应用预条件共轭梯度法和快速傅里叶变换的结合算法（PCGFFT）来求解这个线性代数方程组,其中预条件器选用T.Chan循环预条件共轭梯度法和快速傅里叶变换的结合算法（PCGFFT）来求解这个线性代数方程组,其中预条件器选用T．Chan循环预条件器的二重分块形式。文中给出的数值算例表明该混合技术是有效的,适用于较大的金属栅有限阵列的分析。     

Computation of microstrip S-parameters using a CG-FFT scheme

Several open microstrip structures have been analyzed by using the conjugate gradient fast Fourier transform (CGFFT) method to solve the electric field integral equation (EFIE). The analysis of the microstrip structure provides equivalent electric currents on the conducting patches. Extensive computation is performed in the spectral domain. Windowing techniques are used to improve the accuracy of the method. New models for the microstrip feed and load have been developed in combination with the CGFFT method. Results for the S-parameters are compared with the results of other methods and with measurements. The method appears to be accurate and computationally efficient     

Parallel in-core and out-of-core solution of electrically large problems using the RWG basis functions

Currently, the problem size that can be solved in reasonable time using the Method of Moments is limited by the amount of memory installed in the computer. This paper offers a new development that not only breaks this memory constraint, but also maintains the efficiency of running the problem in-core. In this paper, highly efficient parallel matrix-filling schemes are presented for parallel in-core and parallel out-of-core integral-equation solvers with subdomain RWG basis functions. The parallel methodology for matrix filling is quite different when using a subdomain basis as opposed to using a higher-order basis. The parallel in-core solver uses memory, which is often expensive and limited in size. The parallel out-of-core solver is introduced to extend the capability of MoM to solve larger problems that can be as large as the amount of storage on the hard disk. Numerical results on several typical computer platforms show that the parallel matrix-filling schemes and matrix-equation solvers introduced here are highly efficient and achieve theoretical predictions. The implementation of these advancements with the widely used RWG basis functions creates a powerful tool for efficient computational electromagnetics solution of complex real-world problems.     

自适应交叉近似压缩的高阶矩量法的并行实现

高阶矩量法在计算电磁学中的应用越来越广泛, 为了进一步提高其计算规模, 引入并行的自适应交叉近似压缩算法(Adaptive Cross Approximation algorithm, ACA).该算法首先采用非均匀有理B样条建模(Non-Uniform Rational B-Splines, NURBS)的方法进行面片分组; 然后利用矩量法中远区阻抗矩阵的低秩特性进行ACA压缩; 最后采用稀疏近似逆预条件(Sparse Pattern Approximate Inverse preconditioning, SPAI)的共轭梯度法(Conjugate Gradient method, CG)快速求解矩阵方程.该算法中的ACA压缩过程和迭代求解过程都特别适合并行计算.数值实验表明, 对于电大尺寸问题, ACA压缩后的矩阵占用的内存远远低于原矩阵, 而预条件的共轭梯度法可以很快收敛.此外该算法在大规模并行时的效率较高.     

Cosine transform based preconditioners for total variationdeblurring

In PDE image restoration problems, one has to invert operators which is a sum of a blurring operator and an elliptic operator with highly varying coefficient. We present a preconditioner for such operators, which can be used with the conjugate gradient (CG) method, and compare it with Vogel and Oman's (see SIAM J. Sci. Stat. Comput., vol.17, p.227-38, 1996, and IEEE Trans. Image Processing, vol.7, p.813-24, 1998) product preconditioner.