On some new approximate factorization methods for block tridiagonal matrices suitable for vector and parallel processors

In this paper, to obtain an efficient parallel algorithm to solve sparse block-tridiagonal linear systems, stair matrices are used to construct some parallel polynomial approximate inverse preconditioners. These preconditioners are suitable when the desired goal is to maximize parallelism. Moreover, some theoretical results concerning these preconditioners are presented and how to construct preconditioners effectively for any nonsingular block tridiagonal H-matrices is also described. In addition, the validity of these preconditioners is illustrated with some numerical experiments arising from the second order elliptic partial differential equations and oil reservoir simulations.     

A High Accuracy Post-processing Algorithm for the Eigenvalues of Elliptic Operators

In a very recent paper (Hu et al., The lower bounds for eigenvalues of elliptic operators by nonconforming finite element methods, Preprint, 2010), we prove that the eigenvalues by the nonconforming finite element methods are smaller than the exact ones for the elliptic operators. It is well-known that the conforming finite element methods produce the eigenvalues above to the exact ones. In this paper, we combine these two aspects and derive a new post-processing algorithm to approximate the eigenvalues of elliptic operators. We implement this algorithm and find that it actually yields very high accuracy approximation on very coarser mesh. The numerical results demonstrate that the high accuracy herein is of two fold: the much higher accuracy approximation on the very coarser mesh and the much higher convergence rate than a single lower/upper bound approximation. Moreover, we propose some acceleration technique for the algorithm of the discrete eigenvalue problem based on the solution of the discrete eigenvalue problem which yields the upper bound of the eigenvalue. With this acceleration technique we only need several iterations (two iterations in our example) to find the numerical solution of the discrete eigenvalue problem which produces the lower bound of the eigenvalue. Therefore we only need to solve essentially one discrete eigenvalue problem.     

A Riccati-type algorithm for solving generalized Hermitian eigenvalue problems

The paper describes a heuristic algorithm for solving a generalized Hermitian eigenvalue problem fast. The algorithm searches a subspace for an approximate solution of the problem. If the approximate solution is unacceptable, the subspace is expanded to a larger one, and then, in the expanded subspace a possibly better approximated solution is computed. The algorithm iterates these two steps alternately. Thus, the speed of the convergence of the algorithm depends on how to generate a subspace. In this paper, we derive a Riccati equation whose solution can correct the approximate solution of a generalized Hermitian eigenvalue problem to the exact one. In other words, the solution of the eigenvalue problem can be found if a subspace is expanded by the solution of the Riccati equation. This is a feature the existing algorithms such as the Krylov subspace algorithm implemented in the MATLAB and the Jacobi–Davidson algorithm do not have. However, similar to solving the eigenvalue problem, solving the Riccati equation is time-consuming. We consider solving the Riccati equation with low accuracy and use its approximate solution to expand a subspace. The implementation of this heuristic algorithm is discussed so that the computational cost of the algorithm can be saved. Some experimental results show that the heuristic algorithm converges within fewer iterations and thus requires lesser computational time comparing with the existing algorithms.

     

Methods of solving a polynomial equation for anH∞ optimal control problem for a single-inputsingle-output discrete-time system

A polynomial equation for the H_∞ optimal control problem is reduced to a nonlinear algebraic equation. Two methods are proposed for solving the algebraic equation. One method uses the singularity of a linear algebraic equation as the optimality index. The other gives an approximate solution by solving an eigenvalue problem. A numerical example is presented     

The Tau Method as an analytic tool in the discussion of equivalence results across numerical methods

A Tau Method approximate solution of a given differential equation defined on a compact [a, b] is obtained by adding to the right hand side of the equation a specific minimal polynomial perturbation termH _n(x), which plays the role of a representation of zero in [a,b] by elements of a given subspace of polynomials. Neither discretization nor orthogonality are involved in this process of approximation. However, there are interesting relations between the Tau Method and approximation methods based on the former techniques. In this paper we use equivalence results for collocation and the Tau Method, contributed recently by the authors together with classical results in the literature, to identify precisely the perturbation termH(x) which would generate a Tau Method approximate solution, identical to that generated by some specific discrete methods over a given mesh Π ∈ [a, b]. Finally, we discuss a technique which solves the inverse problem, that is, to find adiscrete perturbed Runge-Kutta scheme which would simulate a prescribed Tau Method. We have chosen, as an example, a Tau Method which recovers the same approximation as an orthogonal expansion method. In this way we close the diagram defined by finite difference methods, collocation schemes, spectral techniques and the Tau Method through a systematic use of the latter as an analytical tool.     

Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

The reliability of polyhedral homotopy continuation methods for solving a polynomial system becomes increasingly important as the dimension of the polynomial system increases. High powers of the homotopy continuation parameter t and ill-conditioned Jacobian matrices encountered in tracing of homotopy paths affect the numerical stability. We present modified homotopy functions with a new homotopy continuation parameter s and various scaling strategies to enhance the numerical stability. Advantages of employing the new homotopy parameter s are discussed. Numerical results are included to illustrate the improved performance of the presented techniques.A considerable part of this work was conducted while this author was visiting Tokyo Institute of Technology. Research supported by Kosef R004-000-2001-00200.     

Symbolic–numeric sparse interpolation of multivariate polynomials

We consider the problem of sparse interpolation of an approximate multivariate black-box polynomial in floating point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust solutions. We note the similarity between the exact Ben-Or/Tiwari sparse interpolation algorithm and the classical Prony’s method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony’s method. We analyse the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications.     

PHoMpara – Parallel Implementation of the Polyhedral Homotopy Continuation Method for Polynomial Systems

The polyhedral homotopy continuation method is known to be a successful method for finding all isolated solutions of a system of polynomial equations. PHoM, an implementation of the method in C++, finds all isolated solutions of a polynomial system by constructing a family of modified polyhedral homotopy functions, tracing the solution curves of the homotopy equations, and verifying the obtained solutions. A software package PHoMpara parallelizes PHoM to solve a polynomial system of large size. Many characteristics of the polyhedral homotopy continuation method make parallel implementation efficient and provide excellent scalability. Numerical results include some large polynomial systems that had not been solved.     

Discrete least-squares technique for eigenvalues. Part I: The one-dimensional case

A discrete least-squares technique for computing the eigenvalues of differential equations is presented. The eigenvalue approximations are obtained in two steps. Firstly, initial approximations of the desired eigenvalues are computed by solving a quadratic matrix eigenvalue problem resulting from the least-squares method applied to the equation under consideration. Secondly, these initial approximations, being of sufficient accuracy in some cases, are improved by using the Gauss-Newton method. Results from numerical experiments are reported that show great efficiency of the proposed technique in solving both regular and singular one-dimensional problems. The high flexibility of the technique enables one to use also the multidomain approach and the trial functions not satisfying any of the prescribed boundary conditions.     

Numerical Integrations and Unit Resolution Multipliers for Domain Decomposition Methods with Nonmatching Grids

In this paper, we are concerned with the non-overlapping domain decomposition method (DDM) with nonmatching grids for three-dimensional problems. The weak continuity of the DDM solution on the interface is imposed by some Lagrange multiplier. We shall first analyze the influence of the numerical integrations over the interface on the (non-conforming) approximate solution. Then we will propose a simple approach to construct multiplier spaces, one of which can be simply spanned by some smooth basis functions with local compact supports, and thus makes the numerical integrations on the interface rather simple and inexpensive. Also it is shown this multiplier space can generate an optimal approximate solution. Numerical results are presented to compare the new method with the point to point method widely used in engineering.     

无线传感网中分布式信号检测的多维特征值算法优化研究

在大规模无线传感网的分布式信号检测中,针对相关性较高并有一定冗余度的数据集,在保证数据采集可信任的情况下,通过高效算法提高精度是重要的研究方向。 提出一种分散功率算法DPM,用于分布式计算样本协方差矩阵的最大特征值,通过将平均共识和迭代功率法相结合,在相对少量样本和有限次数迭代的条件下,实现了协方差矩阵最大特征值的较快收敛速度和较高精度估计。对比MECD算法和DST算法,仿真结果表明,新算法有效减少了信号样本数和迭代次数,收敛速度较快,可获得更高的检测精度。     

Convolution surfaces for arcs and quadratic curves with a varying kernel

A convolution surface is an isosurface in a scalar field defined by convolving a skeleton, comprising of points, curves, surfaces, or volumes, with a potential function. While convolution surfaces are attractive for modeling natural phenomena and objects of complex evolving topology, the analytical evaluation of integrals of convolution models still poses some open problems. This paper presents some novel analytical convolution solutions for arcs and quadratic spline curves with a varying kernel. In addition, we approximate planar higher-degree polynomial spline curves by optimal arc splines within a prescribed tolerance and sum the potential functions of all the arc primitives to approximate the field for the entire spline curve. Published online: November 20, 2002     

On the convergence condition of generalized root iterations for the inclusion of polynomial zeros

Using a fixed point relation based on the logarithmic derivative of the k-th order of an algebraic polynomial and the definition of the k-th root of a disk, a family of interval methods for the simultaneous inclusion of complex zeros in circular complex arithmetic was established by Petković [M.S. Petković, On a generalization of the root iterations for polynomial complex zeros in circular interval arithmetic, Computing 27 (1981) 37–55]. In this paper we give computationally verifiable initial conditions that guarantee the convergence of this parallel family of inclusion methods. These conditions are significantly relaxed compared to the previously stated initial conditions presented in literature.     

Using symmetries in the eigenvalue method for polynomial systems

One way of solving polynomial systems of equations is by computing a Gröbner basis, setting up an eigenvalue problem and then computing the eigenvalues numerically. This so-called eigenvalue method is an excellent bridge between symbolic and numeric computation, enabling the solution of larger systems than with purely symbolic methods. We investigate the case that the system of polynomial equations has symmetries. For systems with symmetry, some matrices in the eigenvalue method turn out to have special structure. The exploitation of this special structure is the aim of this paper. For theoretical development we make use of SAGBI bases of invariant rings. Examples from applications illustrate our new approach.     

A variational approximation method for 2nd order elliptic eigenvalue problems in a composite structure with nonstandard boundary conditions

In this paper we deal with the finite element analysis of a class of eigenvalue problems (EVPs) in a composite structure in the plane, consisting of rectangular subdomains which enclose an intermediate region. Nonlocal boundary conditions (BCs) of Robin type are imposed on the inner boundaries, i.e. on the interfaces of the respective subdomains with the intermediate region. On the eventual interfaces between two subdomains we impose discontinuous transition conditions (TCs). Finally, we have classical local BCs at the outer boundaries. Such problems are related to some heat transfer problems e.g. in a horizontal cross section of a wall enclosing an air cave.     

An Adaptive Version of the Boost by Majority Algorithm

We propose a new boosting algorithm. This boosting algorithm is an adaptive version of the boost by majority algorithm and combines bounded goals of the boost by majority algorithm with the adaptivity of AdaBoost.The method used for making boost-by-majority adaptive is to consider the limit in which each of the boosting iterations makes an infinitesimally small contribution to the process as a whole. This limit can be modeled using the differential equations that govern Brownian motion. The new boosting algorithm, named BrownBoost, is based on finding solutions to these differential equations.The paper describes two methods for finding approximate solutions to the differential equations. The first is a method that results in a provably polynomial time algorithm. The second method, based on the Newton-Raphson minimization procedure, is much more efficient in practice but is not known to be polynomial.     

Derivative Free Inclusion Methods for Polynomial Zeros

Two iterative methods for the simultaneous inclusion of complex zeros of a polynomial are presented. Both methods are realized in circular interval arithmetic and do not use polynomial derivatives. The first method of the fourth order is composed as a combination of interval methods with the order of convergence two and three. The second method is constructed using double application of the inclusion method of Weierstrass’ type in serial mode. It is shown that its R-order of convergence is bounded below by the spectral radius of the corresponding matrix. Numerical examples illustrate the convergence rate of the presented methods     

基于最小特征值非线性修正的快速噪声水平估计算法

鉴于从噪声图像上提取的原生图块协方差矩阵的最小特征值与噪声水平值之间具有显著的相关性,提出一种基于多项式回归技术训练非线性映射模型,直接将原生图块最小特征值修正为最终的噪声水平预测值的快速噪声水平估计算法。首先,选择具有代表性且无失真的自然图像作为训练图像集合;然后,对这些图像施以不同程度的高斯噪声构成样本训练图像库。在此基础上,提取各个噪声样本图像的原生图块, 并使用PCA变化得到原生图块协方差矩阵的最小特征值;最后,利用多项式回归技术构建最小特征值与噪声水平值之间的非线性修正模型。实验表明,与现有算法相比,改进算法对高、中、低各级别的噪声都能鲁棒地进行预测,尤其在低水平噪声方面表现出色,在预测准确度和执行效率两方面具有显著的综合优势。     

Horner's Rule for Interval Evaluation Revisited

Interval arithmetic can be used to enclose the range of a real function over a domain. However, due to some weak properties of interval arithmetic, a computed interval can be much larger than the exact range. This phenomenon is called dependency problem. In this paper, Horner's rule for polynomial interval evaluation is revisited. We introduce a new factorization scheme based on well-known symbolic identities in order to handle the dependency problem of interval arithmetic. The experimental results show an improvement of 25% of the width of computed intervals with respect to Horner's rule. Received December 14, 2001; revised March 27, 2002 Published online: July 8, 2002     

New progress in real and complex polynomial root-finding

Matrix methods are increasingly popular for polynomial root-finding. The idea is to approximate the roots as the eigenvalues of the companion or generalized companion matrix associated with an input polynomial. The algorithms also solve secular equation. QR algorithm is the most customary method for eigen-solving, but we explore the inverse Rayleigh quotient iteration instead, which turns out to be competitive with the most popular root-finders because of its excellence in exploiting matrix structure. To advance the iteration we preprocess the matrix and incorporate Newton’s linearization, repeated squaring, homotopy continuation techniques, and some heuristics. The resulting algorithms accelerate the known numerical root-finders for univariate polynomial and secular equations, and are particularly well suited for the acceleration by using parallel processing. Furthermore, even on serial computers the acceleration is dramatic for numerical approximation of the real roots in the typical case where they are much less numerous than all complex roots.