PARALLEL ITERATION FOR SPLITTING FACTORS OF POLYNOMIALS

In this paper we consider some parallel iterations for splitting quadratic factors of polynomials and their convergence.     

Finding roots of a real polynomial simultaneously by means of Bairstow's method

Aberth's method for finding the roots of a polynomial was shown to be robust. However, complex arithmetic is needed in this method even if the polynomial is real, because it starts with complex initial approximations. A novel method is proposed for real polynomials that does not require any complex arithmetic within iterations. It is based on the observation that Aberth's method is a systematic use of Newton's method. The analogous technique is then applied to Bairstow's procedure in the proposed method. As a result, the method needs half the computations per iteration than Aberth's method. Numerical experiments showed that the new method exhibited a competitive overall performance for the test polynomials.     

同时求多项式全部零点的一族快速并行迭代和区间迭代(Ⅱ)

本文对[1]所提出的一族同时求多项式全部零点的并行迭代兼区间迭代加以进一步的发展。首先,作为纯粹的并行迭代法,我们在§2把每步并行迭代扩展为q个并行子步,这样得到的并行迭代法对只有单零点的多项式的全部零点的收敛是q(p 1)阶的。值得注意的是,在这里阶的提高大大超过了每步计算代价的增加,例如,当q=2时,每步     

PARALLEL IMPLEMENTATIONS OF THE FAST SWEEPING METHOD

The fast sweeping method is an efficient iterative method for hyperbolic problems. It combines Gauss-Seidel iterations with alternating sweeping orderings. In this paper several parallel implementations of the fast sweeping method are presented. These parallel algorithms are simple and efficient due to the causality of the underlying partial different equations. Numerical examples are used to verify our algorithms.     

Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method

In this paper, we propose a Quasi-Orthogonal Matching Pursuit (QOMP) algorithm for constructing a sparse approximation of functions in terms of expansion by orthonormal polynomials. For the two kinds of sampled data, data with noises and without noises, we apply the mutual coherence of measurement matrix to establish the convergence of the QOMP algorithm which can reconstruct $s$-sparse Legendre polynomials, Chebyshev polynomials and trigonometric polynomials in $s$ step iterations. The results are also extended to general bounded orthogonal system including tensor product of these three univariate orthogonal polynomials. Finally, numerical experiments will be presented to verify the effectiveness of the QOMP method.     

Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

基于并行计算的多方向强次可行模松弛SQP算法

本文研究求解非线性约束优化问题.利用多方向并行方法,提出了一个新的强次可行模松弛序列二次规划(SQP)算法.数值试验表明,迭代次数和计算时间少于只取单一参数的传统算法.     

两族选代的不动点和Julia集

This paper proves that, for complex polynomials, all extraneous fixed pointsfor any iteration of Halley iterative family and another relevant iterative family arerepelling. Thus no false convergent phenomenon arises on these iterations.     

Computing roots of polynomials on vector processing machines

The Durand and Kerner algorithm for the computation of roots of polynomials has not been og reat use up to now. The reason is the existence of more efficient methods for computers ofthe SISD type (sequential). Actually vector processing machines such as CRAY-1 or CDC CYBER 205 must bring Durand's algorithm back to honour because of its possibility of extensive vectorization. However, as the method has its maximum efficiency for a polynomial with no multiple root a criterion using Vignes' permutation-perturbation method is given to know whether the roots are all distinct or not. The optimum criterion for stopping the iterations is shown to be vectorizable and some useful properties of the method are given. Numerical examples are considered.     

基于高斯伪谱的最优控制求解及其应用

研究一种基于高斯伪谱法的具有约束受限的最优控制数值计算问题.方法将状态演化和控制规律用多项式参数化近似,微分方程用正交多项式近似.将最优控制问题求解问题转化为一组有约束的非线性规划求解.详细论述了该种近似方法的有效性.作为该种方法的应用,讨论了一个障碍物环境下的机器人最优路径生成问题.将机器人路径规划问题转化为具有约束条件最优控制问题,然后用基于高斯伪谱的方法求解,并给出了仿真结果.     

A SQP METHOD FOR MINIMIZING A CLASS OF NONSMOOTH FUNCTIONS

In this paper,we present a successive quadratic programming(SQP)method for minimizing a class of nonsmooth functions,which are the sum of a convex function and a nonsmooth composite function.The method generates new iterations by using the Armijo-type line search technique after having found the search directions.Global convergence property is established under mild assumptions.Numerical results are also offered.     

A comparison of methods for terminating polynomial iterations

Three methods of terminating polynomial root-finding iterations are compared, one based on explicit calculation of rounding errors, one based on differences in the iterates, and one based on different methods of calculating the polynomial. In extensive experiments with randomly generated polynomials, it was found that the simplest method (based on differences in the iterates) usually gives the lowest actual error in the root.     

On the partial synchronization of iterative methods

The rapidly growing field of parallel computing systems promotes the study of parallel algorithms, with the Monte Carlo method and asynchronous iterations being among the most valuable types. These algorithms have a number of advantages. There is no need for a global time in a parallel system (no need for synchronization), and all computational resources are efficiently loaded (the minimum processor idle time). The method of partial synchronization of iterations for systems of equations was proposed by the authors earlier. In this article, this method is generalized to include the case of nonlinear equations of the form x = F(x), where x is an unknown column vector of length n, and F is an operator from ?ⁿ into ?ⁿ. We consider operators that do not satisfy conditions that are sufficient for the convergence of asynchronous iterations, with simple iterations still converging. In this case, one can specify such an incidence of the operator and such properties of the parallel system that asynchronous iterations fail to converge. Partial synchronization is one of the effective ways to solve this problem. An algorithm is proposed that guarantees the convergence of asynchronous iterations and the Monte Carlo method for the above class of operators. The rate of convergence of the algorithm is estimated. The results can prove useful for solving high-dimensional problems on multiprocessor computational systems.     

Generalized speculative computation of parallel simulated annealing

Simulated annealing is known to be highly sequential due to dependences between iterations. While the conventional speculative computation with a binary tree has been found effective for parallel simulated annealing, its performance is limited to (logp)-fold speedup due to parallel execution of logp iterations onp processors. This report presents a new approach to parallel simulated annealing, calledgeneralized speculative computation (GSC). The GSC is synchronous, maintaining the same decision sequence as sequential simulated annealing. The use of two loop indices encoded in a single integer eliminates broadcasting of central data structure to all processors. The master-slave parallel programming paradigm simplifies controlling the activities ofp iterations which are executed in parallel onp processors. To verify the performance of GSC, we implemented 100-city to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results on the AP1000 demonstrate that the GSC approach can indeed be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.     

Aitken's and Steffensen's accelerations in several variables

Summary Aitken's acceleration of scalar sequences extends to sequences of vectors that behave asymptotically as iterations of a linear transformation. However, the minimal and characteristic polynomials of that transformation must coincide (but the initial sequence of vectors need not converge) for a numerically stable convergence of Aitken's acceleration to occur. Similar results hold for Steffensen's acceleration of the iterations of a function of several variables. First, the iterated function need not be a contracting map in any neighbourhood of its fixed point. Instead, the second partial derivatives need only remain bounded in such a neighbourhood for Steffensen's acceleration to converge quadratically, even if ordinary iterations diverge. Second, at the fixed point the minimal and characteristic polynomials of the Jacobian matrix must coincide to ensure a numerically stable convergence. By generalizing the work that Noda did on the subject between 1981 and 1986, the results presented here explain the numerical observations reported by Henrici in 1964 and 1982.This work was supported by a grant from the Northwest Institute for Advanced Study, an organ of Eastern Washington University     

Solving reactor problems to determine the multiplication: A new method of accelerating outer iterations

A new cyclic iterative method with variable parameters is proposed for accelerating the outer iterations in a process used to calculate K _eff in multigroup problems. The method is based on the use of special extremal polynomials that are distinct from Chebyshev polynomials and take into account the specific nature of the problem. To accelerate the convergence with respect to K _eff, the use of three orthogonal functionals is proposed. Their values simultaneously determine the three maximal eigenvalues. The proposed method was incorporated in the software for neutron-physics calculations for WWER reactors.     

Parallel characteristic finite element method for time‐dependent convection–diffusion problem

Based on the overlapping‐domain decomposition and parallel subspace correction method, a new parallel algorithm is established for solving time‐dependent convection–diffusion problem with characteristic finite element scheme. The algorithm is fully parallel. We analyze the convergence of this algorithm, and study the dependence of the convergent rate on the spacial mesh size, time increment, iteration times and sub‐domains overlapping degree. Both theoretical analysis and numerical results suggest that only one or two iterations are needed to reach to optimal accuracy at each time step. Copyright © 2010 John Wiley & Sons, Ltd.     

求解半线性抛物问题的两种二重网格算法

用线性方法对半线性抛物问题进行求解。方法依赖粗、细二重网格,针对粗解在细网格上的修正提出了两种算法,算法1是乘积倍的增长精度而算法2是平方倍的增长精度,而且重复算法1、2的最后几步可以任意阶地逼近细网格上的非线性解。数值算例验证了算法的可行性和有效性。     

Enriched Methods for Large-Scale Unconstrained Optimization

This paper describes a class of optimization methods that interlace iterations of the limited memory BFGS method (L-BFGS) and a Hessian-free Newton method (HFN) in such a way that the information collected by one type of iteration improves the performance of the other. Curvature information about the objective function is stored in the form of a limited memory matrix, and plays the dual role of preconditioning the inner conjugate gradient iteration in the HFN method and of providing an initial matrix for L-BFGS iterations. The lengths of the L-BFGS and HFN cycles are adjusted dynamically during the course of the optimization. Numerical experiments indicate that the new algorithms are both effective and not sensitive to the choice of parameters.     

ANALYSIS OF A MECHANICAL SOLVER FOR LINEAR SYSTEMS OF EQUATIONS S

1. Introduction/ A new approaCh to solve systems of linear eqttations, equlvaleat to solve the ~ion of adamped harmonic oscillator, has been PrOPosed in a previous paper[11. Due to this parallelism,we call such methods Mechanical Solvers for systems of linear equations. The present study isdevoted to the analysis of these methods.Let be the linear systemwhere we assume that A is an m x m nonsingular matriX (i.e. the system has a ~ solution).We may associate to it the Newton's equation for …