The generalized Goertzel algorithm and its parallel hardware implementation

Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) error correcting codes are widely used in digital technology. An important problem in the implementation of RS and BCH decoding is the fast finding of the error positions (the roots of error locator polynomials). Several fast root-finding algorithms for polynomials over finite fields have been proposed. In this paper we give a generalization of the Goertzel algorithm. Our algorithm is suitable for the parallel hardware implementation and the time of multiplications used is restricted by a constant.     

MULTILEVEL AUGMENTATION METHODS FOR SOLVING OPERATOR EQUATIONS

We introduce multilevel augmentation methods for solving operator equations based on direct sum decompositions of the range space of the operator and the solution space of the operator equation and a matrix splitting scheme. We establish a general setting for the analysis of these methods, showing that the methods yield approximate solutions of the same convergence order as the best approximation from the subspace. These augmentation methods allow us to develop fast, accurate and stable nonconventional numerical algorithms for solving operator equations. In particular, for second kind equations, special splitting techniques are proposed to develop such algorithms. These algorithms are then applied to solve the linear systems resulting from matrix compression schemes using wavelet-like functions for solving Fredholm integral equations of the second kind. For this special case, a complete analysis for computational complexity and convergence order is presented. Numerical examples are included to demonstra     

Edge-Weighted Centroidal Voronoi Tessellations

<正>Most existing applications of centroidal Voronoi tessellations(CVTs) lack consideration of the length of the cluster boundaries.In this paper we propose a new model and algorithms to produce segmentations which would minimize the total energy—a sum of the classic CVT energy and the weighted length of cluster boundaries.To distinguish it with the classic CVTs,we call it an Edge-Weighted CVT(EWCVT).The concept of EWCVT is expected to build a mathematical base for all CVT related data classifications with requirement of smoothness of the cluster boundaries.The EWCVT method is easy in implementation,fast in computation,and natural for any number of clusters.     

基于中心路径大邻域上的一类非单调线性互补问题的高阶可行内点算法

In this paper a high-order feasible interior point algorithm for a class of nonmonotonic (P-matrix) linear complementary problem based on large neighborhoods of central path is presented and its iteration complexity is discussed.These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms bound depends on the size of the neighborhood. It is well known that the complexity of large-step algorithms is greater than that of short- step ones. By using high-order power series (hence the name high-order algorithms), the iteration complexity can be reduced. We show that the upper bound of complexity for our high-order algorithms is equal to that for short-step algorithms.     

QR factorization for row or column symmetric matrix

The problem of fast computing the QR factorization of row or column symmetric matrix is considered. We address two new algorithms based on a correspondence of Q and R matrices between the row or column symmetric matrix and its mother matrix. Theoretical analysis and numerical evidence show that, for a class of row or column symmetric matrices, the QR factorization using the mother matrix rather than the row or column symmetric matrix per se can save dramatically the CPU time and memory without loss of any numerical precision.     

Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.     

Chebfun and numerical quadrature

Chebfun is a Matlab-based software system that overloads Matlab's discrete operations for vectors and matrices to analogous continuous operations for functions and operators.We begin by describing Chebfun's fast capabilities for Clenshaw-Curtis and also Gauss-Legendre,-Jacobi,-Hermite,and-Laguerre quadrature,based on algorithms of Waldvogel and Glaser,Liu and Rokhlin.Then we consider how such methods can be applied to quadrature problems including 2D integrals over rectangles,fractional derivatives and integrals,functions defined on unbounded intervals,and the fast computation of weights for barycentric interpolation.     

Algorithms for Finding the Inverses of Factor Block Circulant Matrices

In this paper,algorithms for finding the inverse of a factor block circulant matrix, a factor block retrocirculant matrix and partitioned matrix with factor block circulant blocks over the complex field are presented respectively.In addition,two algorithms for the inverse of a factor block circulant matrix over the quaternion division algebra are proposed.     

STABILITY OF INERTIAL ALGORITHMS*

This paper describes some inertial algorithms for the approximation of nonlincar evolution equations and studies a priori estimates of the approximate solutiom and the stability of the inertial algorithms.     

Some Remarks on the Convex Feasibility Problem and Best Approximation Problem

In this paper we investigate several solution algorithms for the convex fea- sibility problem(CFP)and the best approximation problem(BAP)respectively.The algorithms analyzed are already known before,but by adequately reformulating the CFP or the BAP we naturally deduce the general projection method for the CFP from well-known steepest decent method for unconstrained optimization and we also give a natural strategy of updating weight parameters.In the linear case we show the connec- tion of the two projection algorithms for the CFP and the BAP respectively.In addition, we establish the convergence of a method for the BAP under milder assumptions in the linear case.We also show by examples a Bauschke's conjecture is only partially correct.     

修正的TV-Stokes模型的新快速算法

基于Tai等人的前期工作,本文研究修正的TV-Stokes图像去噪模型,提出一些新的求解该两步模型的快速算法.我们利用对偶形式和多重网格方法得到一个求解第1步的快速算法.给出另外一种新的求解光滑的切向量场的保不可压性质的算法.在第2步中,我们提出一类有效的全新算法:首先通过计算Poisson方程得到具有光滑法向量场的函数g,然后利用Jia和Zhao的方法得到恢复的图像.新算法的运算速度非常快,用于图像恢复的CPU时间少于0.1 s.数值结果显示新的快速算法是有效的和稳定的,恢复图像的质量也超过了一般去噪方法.     

解不适定问题的一种多尺度方法

1 前言 数学物理反问题是应用数学领域中成长和发展最快的领域之一.反问题大多是不适定的.对于不适定问题的解法已有不少的学者进行探索和研究,Tikhonov正则化方法是一种理论上最完备而在实践上行之有效的方法(参见[5,6,7,8,13]).     

Spectral discretizations of 3-D elliptic problems and fast domain decomposition methods

An important for applications, the class of hp discretizations of second-order elliptic equations consists of discretizations based on spectral finite elements. The development of fast domain decomposition algorithms for them was restrained by the absence of fast solvers for the basic components of the method, i.e., for local interior problems on decomposition subdomains and their faces. Recently, the authors have established that such solvers can be designed using special factorized preconditioners. In turn, factorized preconditioners are constructed using an important analogy between the stiffness matrices of spectral and hierarchical basis hp-elements (coordinate functions of the latter are defined as tensor products of integrated Legendre polynomials). Due to this analogy, for matrices of spectral elements, fast solvers can be developed that are similar to those for matrices of hierarchical elements. Based on these facts and previous results on the preconditioning of other components, fast domain decomposition algorithms for spectral discretizations are obtained.     

Fast proximal algorithms for nonsmooth convex optimization

In the lines of our previous approach to devise proximal algorithms for nonsmooth convex optimization by applying Nesterov fast gradient concept to the Moreau–Yosida regularization of a convex function, we develop three new proximal algorithms for nonsmooth convex optimization. In these algorithms, the errors in computing approximate solutions for the Moreau–Yosida regularization are not fixed beforehand, while preserving the complexity estimates already established. We report some preliminary computational results to give a first estimate of their performance.     

Analysis of a Diagonal Form of the Fast Multipole Algorithm for Scattering Theory

Discretisation of the integral equations of acoustic scattering yields a system of linear equations with full coefficient matrices. In recent years a number of fast algorithms for the solution of this system have been proposed. In this paper we present a complete analysis for a fast multipole method for the Helmholtz equation. A one-level diagonal form of the multipole method is applied to a hypersingular integral equation arising from 2d scattering theory. The error of the approximation is analysed and the results used to establish the complexity of the method.     

Fast algorithms for floating-point interval matrix multiplication

We discuss several methods for real interval matrix multiplication. First, earlier studies of fast algorithms for interval matrix multiplication are introduced: naive interval arithmetic, interval arithmetic by midpoint-radius form by Oishi-Rump and its fast variant by Ogita-Oishi. Next, three new and fast algorithms are developed. The proposed algorithms require one, two or three matrix products, respectively. The point is that our algorithms quickly predict which terms become dominant radii in interval computations. We propose a hybrid method to predict which algorithm is suitable for optimizing performance and width of the result. Numerical examples are presented to show the efficiency of the proposed algorithms.     

AN ADAPTIVE NONMONOTONIC TRUST REGION METHOD WITH CURVILINEAR SEARCHES

In this paper,an algorithm for unconstrained optimization that employs both trustregion techniques and curvilinear searches is proposed.At every iteration,we solve thetrust region subproblem whose radius is generated adaptively only once.Nonmonotonicbacktracking curvilinear searches are performed when the solution of the subproblem isunacceptable.The global convergence and fast local convergence rate of the proposedalgorithms are established under some reasonable conditions.The results of numericalexperiments are reported to show the effectiveness of the proposed algorithms.     

Roundoff error analysis of fast DCT algorithms in fixed point arithmetic

Discrete cosine transforms (DCT) are essential tools in numerical analysis and digital signal processing. Processors in digital signal processing often use fixed point arithmetic. In this paper, we consider the numerical stability of fast DCT algorithms in fixed point arithmetic. The fast DCT algorithms are based on known factorizations of the corresponding cosine matrices into products of sparse, orthogonal matrices of simple structure. These algorithms are completely recursive, are easy to implement and use only permutations, scaling, butterfly operations, and plane rotations/rotation-reflections. In comparison with other fast DCT algorithms, these algorithms have low arithmetic costs. Using von Neumann–Goldstine’s model of fixed point arithmetic, we present a detailed roundoff error analysis for fast DCT algorithms in fixed point arithmetic. Numerical tests demonstrate the performance of our results.      

Global and local convergence of a class of penalty-free-type methods for nonlinear programming

We present a class of trust region algorithms without using a penalty function or a filter for nonlinear inequality constrained optimization and analyze their global and local convergence. In each iteration, the algorithms reduce the value of objective function or the measure of constraints violation according to the relationship between optimality and feasibility. A sequence of steps focused on improving optimality is referred to as an f-loop, while some restoration phase focuses on improving feasibility and is called an h-loop. In an f-loop, the algorithms compute trial step by solving a classic QP subproblem rather than using composite-step strategy. Global convergence is ensured by requiring the constraints violation of each iteration not to exceed an progressively tighter bound on constraints violation. By using a second order correction strategy based on active set identification technique, Marato’s effect is avoided and fast local convergence is shown. The preliminary numerical results are encouraging.