Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices

This report may be considered as a non-trivial extension of an unpublished report by William Kahan (Accurate Eigenvalues of a symmetric tri-diagonal matrix, Technical Report CS 41, Computer Science Department, Stanford University, 1966). His interplay between matrix theory and computer arithmetic led to the development of algorithms for computing accurate eigenvalues and singular values. His report is generally considered as the precursor for the development of IEEE standard 754 for binary arithmetic. This standard has been universally adopted by virtually all PC, workstation and midrange hardware manufactures and tens of billions of such machines have been produced. Now we use the features in this standard to improve the original algorithm.In this paper, we describe an algorithm in floating-point arithmetic to compute the exact inertia of a real symmetric (shifted) tridiagonal matrix. The inertia, denoted by the integer triplet (π, ν, ζ), is defined as the number of positive, negative and zero eigenvalues of a real symmetric (or complex Hermitian) matrix and the adjective exact refers to the eigenvalues computed in exact arithmetic. This requires the floating-point computation of the diagonal matrix D of the LDL^t factorization of the shifted tridiagonal matrix T − τI with +∞ and −∞ rounding modes defined in IEEE 754 standard. We are not aware of any other algorithm which gives the exact answer to a numerical problem when implemented in floating-point arithmetic in standard working precisions. The guaranteed intervals for eigenvalues are obtained by bisection or multisection with this exact inertia information. Similarly, using the Golub-Kahan form, guaranteed intervals for singular values of bidiagonal matrices can be computed. The diameter of the eigenvalue (singular value) intervals depends on the number of shifts with inconsistent inertia in two rounding modes. Our algorithm not only guarantees the accuracy of the solutions but is also consistent across different IEEE 754 standard compliant architectures. The unprecedented accuracy provided by our algorithms could be also used to debug and validate standard floating-point algorithms for computation of eigenvalues (singular values). Accurate eigenvalues (singular values) are also required by certain algorithms to compute accurate eigenvectors (singular vectors).We demonstrate the accuracy of our algorithms by using standard matrix examples. For the Wilkinson matrix, the eigenvalues (in IEEE double precision) are very accurate with an (open) interval diameter of 6 ulps (units of the last place held of the mantissa) for one of the eigenvalues and lesser (down to 2 ulps) for others. These results are consistent across many architectures including Intel, AMD, SGI and DEC Alpha. However, by enabling IEEE double extended precision arithmetic in Intel/AMD 32-bit architectures at no extra computational cost, the (open) interval diameters were reduced to one ulp, which is the best possible solution for this problem. We have also computed the eigenvalues of a tridiagonal matrix which manifests in Gauss-Laguerre quadrature and the results are extremely good in double extended precision but less so in double precision. To demonstrate the accuracy of computed singular values, we have also computed the eigenvalues of the Kac₃₀ matrix, which is the Golub-Kahan form of a bidiagonal matrix. The tridiagonal matrix has known integer eigenvalues. The bidiagonal Cholesky factor of the Gauss-Laguerre tridiagonal is also included in the singular value study.     

A verified method for bounding clusters of zeros of analytic functions

In this paper, we propose a verified method for bounding clusters of zeros of analytic functions. Our method gives a disk that contains a cluster of m   zeros of an analytic function f(z)$f(z)$. Complex circular arithmetic is used to perform a validated computation of n  -degree Taylor polynomial p(z)$p(z)$ of f(z)$f(z)$. Some well known formulae for bounding zeros of a polynomial are used to compute a disk containing a cluster of zeros of p(z)$p(z)$. A validated computation of an upper bound for Taylor remainder series of f(z)$f(z)$ and a lower bound of p(z)$p(z)$ on a circle are performed. Based on these results, Rouché's theorem is used to verify that the disk contains the cluster of zeros of f(z)$f(z)$. This method is efficient in computation of the initial disk of a method for finding validated polynomial factor of an analytic function. Numerical examples are presented to illustrate the efficiency of the proposed method.     

油资源运移聚集并行数值模拟和分析

多层油资源运移聚集并行数值模拟,其功能是重建油气盆地的运移聚集演化史,对于油资源的评价,确度油藏位置,估计油藏贮量均具有重要的价值.从生产实际出发,提出数学模型,构造大规模精细并行计算的耦合算子分裂隐式迭代格式,设计了并行计算程序和并行计算的信息传递和交替方向网格剖分方法.并对不同的网格步长进行了并行计算和分析.对滩海地区进行精细数值模拟,计算结果在油田位置等方面和实际情况相吻合.对模型问题(非线型性耦合问题)进行数值分析,得到最佳阶L²误差估计,解决了这一计算渗流力学和石油地质的困难问题.     

模糊桁架结构在模糊激励下的动力响应分析

研究了模糊参数桁架结构在模糊荷载激励下的动力响应分析问题. 不仅模糊桁架结构的物 理参数、几何尺寸具有模糊性,而且外载荷幅值也具有模糊性时,从Duhamel积分式出发,利用模糊因子法、区间运算和振型叠加法求出了结构动力响应模糊变量的表达式. 最后通过算例考察了结构参数和作用荷载的模糊性对结构动力响应的影响,表明所提出的计算模型和 分析方法是正确与可行的.     

On the Additive Group Structure of the Nonstandard Models of the Theory of Integers

Let $\hat \mathbb{Z}$ denote the inverse limit of all finite cyclic groups. Let F, G and H be abelian groups with H ≤ G. Let FβH denote the abelian group (F × H, +^β), where +^βis defined by (a, x) +^β (b, y) = (a + b, x + y + β(a) + β(b) — β(a + b)) for a certain β : F → G linear mod H meaning that β(0) = 0 and β(a) + β(b) — β(a + b) ∈ H for all a, b in F. In this paper we show that the following hold: (1) The additive group of any nonstandard model ℤ* of the ring ℤ is isomorphic to (ℤ*₊/H)βH for a certain β : ℤ*₊/H → $\hat \mathbb{Z}$ linear mod H. (2) $\hat \mathbb{Z}$ is isomorphic to (ℤ₊/H )βH for some β : $\hat \mathbb{Z}$/H →ℚ linear mod H, though $\hat \mathbb{Z}$ is not the additive group of any model of Th(ℤ, +, ×) and the exact sequence H → $\hat \mathbb{Z}$ → $\hat \mathbb{Z}$/H is not splitting.     

RTCM算法在一维光子晶体缺陷模中的应用

利用RTCM算法研究一维光子晶体的缺陷模.研究了TE波和TM波入射时的情况,通过改变杂质层的光学厚度以及杂质层的折射率从而得出一些有重要指导意义的缺陷模特性.同时对有缺陷的一维光子晶体在窄带滤波器中的应用做了一定程度的探讨.结果表明:正入射时,TE波和TM波的透射率几乎相同,随着杂质层光学厚度的增加,透射峰数目增加,这有助于制作多道窄带滤波器.因此,有缺陷的一维光子晶体可以制作波分复用中的多道滤波器.     

On Models Constructed by Means of the Arithmetized Completeness Theorem

In this paper we study the model theory of extensions of models of first‐order Peano Arithmetic (PA) by means of the arithmetized completeness theorem (ACT) applied to a definable complete extension of PA in the original model. This leads us to many interesting model theoretic properties equivalent to reflection principles and ω‐consistency, and these properties together with the associated first‐order schemes extending PA are studied.     

On the application of extended precision arithmetic to quantum mechanical calculations

The computer arithmetic of extended precision has been successfully applied to the problem of a hydrogen atom in an external magnetic field. The solution of the problem was obtained in the analytical form as a double series in nonseparable coordinates. Quantitative results were obtained by direct numerical summation of the series using software-emulated arithmetic of extended precision. Technical aspects of the numerical technique and its possible applications to other practical problems are discussed. © 1997 John Wiley & Sons, Inc. Int J Quant Chem 62: 593–601, 1997     

关于Neuman-Sándor平均的一些特殊组合不等式

研究了Neuman-Sándor平均NS(a,b)关于调和平均H(a,b)、算术平均A(a,b)、二次平均Q(a,b)若干特殊组合的序关系,给出最佳参数α₁,α₂,α₃,α₁₄,β₁,β₂,β₃,β₄∈(0,1),使得下列双向不等式：$\sqrt{a_{1}Q^{2}(a,b)+(1-a_{1})A^{2}(a,b)}< NS(a,b)<\sqrt{\beta_{1}Q^{2}(a,b)+(1-\beta_{1})A^{2}(a,b),}\\ \sqrt{[a_{2}Q(a,b)+(1-a_{2})A(a,b)]A(a,b)}< NS(a,b)<\sqrt{[\beta_{2}Q(a,b)+(1-\beta_{2})A(a,b)]A(a,b),}\\ \sqrt{a_{e}Q^{2}(a,b)+(1-a_{3})H^{2}(a,b)}< NS(a,b)<\sqrt{\beta_{3}Q^{2}(a,b)+(1-\beta_{3})H^{2}(a,b),}\\ \sqrt{[a_{4}Q(a,b)+(1-a_{4})H(a,b)]A(a,b)}< NS(a,b)<\sqrt{[\beta_{4}Q(a,b)+(1-\beta_{4})H(a,b)]A(a,b),}$对所有不同的正实数a和b均成立。