大型对称变带宽方程组的Cholesky分解法

作者针对地球物理数值模拟中常碰到的大型稀疏变带宽方程组的求解问题,介绍了 大型稀疏变带宽矩阵的存储方法及Ｃｈｏｌｅｓｋｙ分解法,该方法的特点是用二个一维数组,其中一个输入时存储对称稀疏矩阵变带宽内的元素,输出时存储Ｃｈｌｏｅｓｋｙ下三角短阵带宽内的元素;另一个存储对称变带宽矩阵对角线元素在前一维数组中的位置,大大节约了所占的计算内存空间。     

LANCZOS迭代算法及其在三维地电场数值模拟计算中的应用研究

在三维电阻率的正演计算中往往涉及到快速、准确求解大型线性方程纽Ax=b的问题。通过采用有限差分法来构造出求解点电源三维地电场的大型稀疏对称线性方程组。并引入Lanczos迭代技术，构造出三对角阵方程组，然后采用正交分解法进行求解，它是Krylov子空间方法中的一种。与传统迭代算法相比，它占用内存少，收敛速度快且稳定。针对大型稀疏矩阵及MATLAB语言的特点，采用简单记录矩阵的非零元素值及其所在行、列值的方法存储大型稀疏矩阵，可大大节省机器内存，提高运算速度。理论分析和计算实例显示，此算法是地电三维正演计算的有效方法，为下一步的反演计算打好基础。     

不完全LU分解预条件BICGSTAB算法实现感应测井二维FDFD快速正演模拟

在柱坐标系下推导了二维感应测井差分格式,采用频率域有限差分方法求解感应测井正演问题。针对差分近似得到的线性方程组系数矩阵是大型稀疏复系数病态矩阵求解困难等问题,采用不完全LU分解预条件的稳定双共轭梯度(BICGSTAB)算法求解该线性方程组。研究结果表明,本算法具有速度快、精度高和稳定性好等优点,能有效提高感应测井正演模拟的效率和精度。     

基于有限单元法的二维／三维大地电磁正演模拟策略

对于二维和三维大地电磁正演问题,有限单元法最后形成了一个线性方程组KX=p。方程组中的K是大型稀疏的带状对称复系数矩阵,其条件数远大于1,为严重病态矩阵,求解其对应方程组会遇到很多困难。不完全LU分解处理的BICGSTAB算法,可用于该线性方程组的求解,并且具有速度快,精度高,稳定性好等优点。为了模拟无穷远边界及满足计算机的内存需求,在保证计算精度的情况下,设计了非均匀网格剖分。在程序编制中,因只存储有限元系数矩阵的非零元素,大大减少了正演计算的时间。通过对二维模型和三维模型电磁响应的计算,验证了该算法的正确性。     

迭代法中压缩对角存储的应用框架

在许多有限元、有限差分的应用中,待解方程组的系数矩阵是大型稀疏带状阵,方程组的求解一般使用迭代法.与其它存储方式相比,压缩对角存储由于不存矩阵元素的行列索引,对内存的使用最为节省.使用压缩对角存储,沿对角线操作可以完成高效的矩阵—向量乘.由于在以往的文献中,没有提及按行、列操作的算法,压缩对角存储的应用范围受到一定的限制.用行、列、对角版的矩阵—向量乘代表普通意义的行、列、对角方向操作模式,通过等价矩阵推导和伪代码,给出了一个包括按行、列操作算法在内的应用框架.这里运用C语言实现不完全Cholesky分解共轭梯度法解方程,阐述了如何在实际编程中使用这个算法框架.经理论与实验分析表明,对角压缩存储应用于框架中是高效的,因为与使用常用的一维行索引存储格式所编程序相比,同样迭代次数的耗时减少了约25％.     

频率域反射波全波形速度反演

全波形反演不仅利用相位和振幅信息,还利用波形的细节变化,具有刻画模型精确细节的能力.在对稀疏矩阵直接LU分解求解的基础上,采用梯度预处理方法对声波介质速度模型进行了反射波全波形反演.采用误差反向传播算法计算目标函数梯度以及伪Hessian矩阵的对角线元素来做梯度预处理.数值模型的实验结果表明,利用有效的频率段便能反演出分辨率较高的速度结构,用低频反演出的结果作为高频反演的初始模型,减少了解的非唯一性.二维高斯光滑初始模型提供了有利的低频信息,得到较好的反演结果.伪Hessian矩阵的预处理吸收了高斯牛顿法的二次收敛优势,在不增加计算量的前提下,加快收敛速度.      

稀疏矩阵快速回代的Cholesky分解法

采用一维压缩存储正演计算中的对称稀疏矩阵,进行Cholesky分解,利用分解后二个矩阵的对称性和稀疏性,对占用时间较多的回代过程采用先消去列的方法,实现快速回代.算例表明,采用该方法,对于点源场的求解与传统顺代回代求解法对比可以提高五倍的速度,对于大地电磁的正演问题,提高了二倍的速度.     

三维电阻率正演计算中的Lanczos迭代算法

在三维电阻率的正反演计算中,快速、准确的正演计算是反演的关键。而正演计算往往涉及到求解大型线性方程组Ax=b的问题,通过Lanczos迭代构造出对称三对角阵方程组,并采用正交分解法进行求解,与传统算法相比,此算法占用内存少、收敛速度快、且稳定;针对大型稀疏矩阵的特点,采用简单地记录矩阵的非零元素值及其所在行、列值的方法,来存储大型稀疏矩阵,可大大节省机器内存,提高运算速度。通过理论分析和点电源三维地电场计算实例,阐述该法是地电三维正演计算的有效方法。     

三维地电场数值计算中的LANCZOS迭代过程及其改进算法

针对三维地电场正演数值计算过程中形成的超大规模稀疏线性方程组,在分析此类线性方程组的一般解法基础上,着重阐述一种适宜求解此类方程组的Lanczos迭代过程与算法原理。同时,当地下介质的电性差异较大时,形成系数矩阵A的条件数就很大,可对算法进行适当改进。讨论采用不完全Cholesky分解方法进行预条件处理,经过条件数改善后,形成新的线性方程组系数矩阵,就会变为一个近似的单位矩阵。经改进后的Lanczos算法,将提高数值计算稳定性,从而加快迭代收敛速度,为提高反演质量提供基础。     

矩阵相乘的压缩存储算法

介绍了对稀疏矩阵进行压缩存储时,稀疏矩阵相乘运算的基本思想和算法.在此基础上,探讨了避免矩阵中零元素相乘的无效操作,奠定了该算法的矩阵变换基础.     

A method for determining the reversibility of a Markov sequence

This paper describes, given a tally matrix with strictly positive entries, a method to determine whether the associated Markov process is reversible, and (for reversible Markov processes) methods to compute the reversibility matrix from the tally matrix. If the tally matrixN is symmetric, then it is shown that the Markov process must be reversible and the reversibility matrixC equalss (R ^–1NR^–1), whereR is the diagonal matrix whosei ^th diagonal entry is the sum of the entries of thei ^th row ofN (for everyi) ands denotes the sum of all the entries ofN. Because a symmetric tally matrix is of special importance in applications, a ² test is proposed for determining, in the presence of experimental errors, whether such a matrix is symmetric.     

Quasi-Symmetry and Reversible Markov Sequences in Sedimentary Sections

Quasi-symmetry can be defined as a purely mathematical property of a matrix—that is, any matrix whose entries are strictly positive possesses quasi-symmetry if it can be written as a product of a diagonal and a symmetric matrix. A unique inverse solution for a quasi-symmetric matrix is readily obtained when the nondiagonal elements of the symmetric and quasi-symmetric matrix are set equal. Then it is shown that a Markov sequence is reversible if and only if it has a quasi-symmetric tally matrix. Because a properly counted Markov sequence must have marginal homogeneity, a simple chi-square test for symmetry on the tally matrix is sufficient to determine if an observed matrix is symmetrical and hence whether the Markov chain is reversible. Applications to sedimentary sequences are illustrated by the use of classical examples and with cyclothem data to determine if the sequence conforms to a reversible or nonreversible Markov process. Should the tally matrix lack marginal homogeneity, it is likely that a sampling bias was introduced by the counting procedure. However, a chi-square test for symmetry on a direct inverse of the tally matrix can be used to determine if the sedimentary sequence conforms to a reversible or a non-reversible Markov process.     

Finite element methods for geothermal reservoir simulation

Two finite element algorithms suitable for long term simulation of geothermal reservoirs are presented. Both methods use a diagonal mass matrix and a Newton iteration scheme. The first scheme solves the 2N unsymmetric algebraic equations resulting from the finite element discretization of the equations governing the flow of heat and mass in porous media by using a banded equation solver. The second method, suitable for problems in which the transmissibility terms are small compared to the accumulation terms, reduces the set of N equations for the Newton corrections to a symmetric system. Comparison with finite difference schemes indicates that the proposed algorithms are competitive with existing methods.     

Tests of Significance for Structural Correlations in the Linear Model of Coregionalization

In the linear model of coregionalization (LMC), when applicable to the experimental direct variograms and the experimental cross variogram computed for two random functions, the variability of and relationships between the random functions are modeled with the same basis functions. In particular, structural correlations can be defined from entries of sill matrices (coregionalization matrices) under second-order stationarity. In this article, modified t-tests are proposed for assessing the statistical significance of estimated structural correlations. Their specific aspects and fundamental differences, compared with an existing modified t-test for global correlation analysis with spatial data, are discussed via estimated effective sample sizes, in relation to the superimposition of random structural components, the range of autocorrelation, the presence of correlation at another structure, and the sampling scheme. Accordingly, simulation results are presented for one structure versus two structures (one without and the other with autocorrelation). The performance of tests is shown to be related to the uncertainty associated with the estimation of variogram model parameters (range, sill matrix entries), because these are involved in the test statistic and the degrees of freedom of the associated t-distribution through the estimated effective sample size. Under the second-order stationarity and LMC assumptions, the proposed tests are generally valid.     

Efficient solution of 3-D geomechanical problems by indirect BEM using iterative methods

The research herein primarily addresses to geomechanical problems of underground constructions in Mining and Civil Engineering. The problems are solved using the Indirect Boundary Element Method (IBEM). Although the geometry of the constructions themselves is usually very complicated, it will become much more complicated if we were to draw the existing joints. The computational problem therefore is how to deal with huge amount of equations and find out efficient methods of their formation and solution keeping in mind restraints of the computer memory and calculation time. Several approaches are used to enhance the performance of the Indirect Boundary Element Method. One of them deals with application of efficient equation solvers. It is shown that Krylov-type methods like CGS and GMRES with simple Jacoby preconditioning appear to be efficient and robust. In addition, adaptive integration on the boundary elements, together with diagonal dominance of equationsmake it possible to accelerate convergence of the iterative procedure. Some of the problems discussed allow a substantial reduction of matrix entries that leads to a very cheap iterative solution keeping reasonable accuracy of the results. © 1998 John Wiley & Sons, Ltd.     

Finite volume discretization with imposed flux continuity for the general tensor pressure equation

We present a new family of flux continuous, locally conservative, finite volume schemes applicable to the diagonal and full tensor pressure equations with generally discontinuous coefficients. For a uniformly constant symmetric elliptic tensor field, the full tensor discretization is second order accurate with a symmetric positive definite matrix. For a full tensor, an _M-matrix with diagonal dominance can be obtained subject to a sufficient condition for ellipticity. Positive definiteness of the discrete system is illustrated. Convergence rates for discontinuous coefficients are presented and the importance of modeling the full permeability tensor pressure equation is demonstrated.     

The composition of carbonaceous chondrite matrix

Matrix compositions of 32 carbonaceous chondrites have been analyzed by an electron microprobe defocussed-beam technique. Except in those chondrites that show evidence of metamorphism, matrices are compositionally similar and have correlation coefficients of +0.96 or greater. Weight per cent Mg/Si in matrices is constant (0.82 ± 0.05) but less than ratios derived from bulk analyses. Matrices in metamorphosed meteorites are Mg-depleted relative to those of other chondrites. Al Rais and Renazzo (anomalous by any classification scheme) have Mg-enriched matrices. Average matrix compositions cluster into chemical subgroups similar to those based on bulk chemical and petrographie criteria [C1, C2, C3(0), C3(V)]. C1 matrices are particularly variable in composition from point to point within the same meteorite, but points within individual breccia clasts appear to be more compositionally uniform. Cl matrices are depleted in Na, S, and Ca relative to solar and C2 matrix values, probably as a result of leaching. Matrix Ca/A1 ratios are highly variable and generally fall below the accepted meteoritic value. The only strong interelement correlation is for Fe, Ni, and S in C2 matrices, suggesting mixing of variable proportions of two components: Mg-rich phyllosilicate and a Ni-bearing chalcophile phase. The amount of magnetite associated with C2 matrix appears to vary systematically with matrix composition. Isotopic, chemical, and mineralogical constraints suggest that matrix, although appreciably altered in some meteorites, is chiefly a solar system condensation product which contains an admixture of unprocessed interstellar dust.     

An improved accelerated initial stress procedure for elasto-plastic finite element analysis

The most flexible and generally applicable methods for elasto-plastic analysis are those based on an incremental-iterative form of the initial stress approach, but such methods often exhibit slow convergence. The acceleration procedure known as the alpha-constant stiffness method is reconsidered and some modifications are proposed. The principal difference in the present approach lies in the use of a single acceleration parameter, rather than a diagonal matrix of acceleration coefficients. The new scheme shows a significant improvement in numerical stability and converges three times faster than the standard initial stress method. Some practical aspects associated with the method are discussed and a number of applications are presented.     

GPU-accelerated iterative solutions for finite element analysis of soil–structure interaction problems

Soil–structure interaction problems are commonly encountered in engineering practice, and the resulting linear systems of equations are difficult to solve due to the significant material stiffness contrast. In this study, a novel partitioned block preconditioner in conjunction with the Krylov subspace iterative method symmetric quasiminimal residual is proposed to solve such linear equations. The performance of these investigated preconditioners is evaluated and compared on both the CPU architecture and the hybrid CPU–graphics processing units (GPU) computing environment. On the hybrid CPU–GPU computing platform, the capability of GPU in parallel implementation and high-intensity floating point operations is exploited to accelerate the iterative solutions, and particular attention is paid to the matrix–vector multiplications involved in the iterative process. Based on a pile-group foundation example and a tunneling example, numerical results show that the partitioned block preconditioners investigated are very efficient for the soil–structure interaction problems. However, their comparative performances may apparently depend on the computer architecture. When the CPU computer architecture is used, the novel partitioned block symmetric successive over-relaxation preconditioner appears to be the most efficient, but when the hybrid CPU–GPU computer architecture is adopted, it is shown that the inexact block diagonal preconditioners embedded with simple diagonal approximation to the soil block outperform the others.