对称r-循环矩阵的快速算法和并行算法

借助于快速付立叶变换(FFT),给出了一种判断对称r-循环线性系统是否有解的快速算法,并且在有解的情况下求出其解,该算法的计算复杂度为O(nlogn),且具有很好的并行性,若使用n台处理机并行处理该算法则只需要O(logn)步.当r=0时,对称r-循环矩阵变成一个上三角型Hankel矩阵,我们也给出了此类矩阵求逆的一种算法.最后将该算法推广到线性同余系统,其运算量仅为O(nlogn).     

WDM网络中的一个改进的最优半光通道路由算法

本文在一个限定的条件下，提出了一个WDM网络中的寻找最优半光通道算法，使时间复杂度从O（k^2n km knlog(kn))提高到O（k^2n km nlogn)。     

多重三角T阵与多元多项式的快速除法

我们在[1]中给出了求三角形T矩阵的逆和计算一元多项式除法的O(nlogn)算法,改进了这两个问题已有的工作量为O(nlog~2n)的快速算法。本文给出了多重三角T阵的乘积、求逆和多元多项式的快速除法等快速方法,推广了[1]和[2]的结果。为叙述简便,我们仅就二重上三角形T阵与二元多项式除法讨论。由此不难推广到一般情形。     

关于多项式矩阵的快速除法

本文讨论了分块 T 型三角矩阵求逆和多项式矩阵除法的 O(k~2nlogn)快速算法,推广了文[3]的结果.     

离线k-服务器问题算法的改进

阐述了在k-服务器猜想的证明中改进经典的离线k-服务器问题算法的必要性,从而对经典算法进行了改进,设计了一种新算法,其复杂度由原来的O(m(nk)2)下降为O(mk2).     

基于核函数求解线性互补问题的不可行内点算法

本文研究了线性互补问题内点算法.利用全牛顿步长求解迭代方向,获得了算法迭代复杂性为O(nlogn/ε),推广了Roos等关于线性规划问题不可行内点算法,其复杂性与目前最好的不可行内点算法复杂性一致.     

基于全牛顿步长求解凸二次规划问题的不可行内点算法

借助于全牛顿步长对凸二次规划问题提出了一种新的不可行内点算法.算法主要迭代由可行迭代步和中心路径邻域迭代步组成.其优点是线性搜寻方向是不需要的.最后证明算法迭代复杂性为O(nlogn/ε),与目前最好的不可行内点算法复杂性一致.     

块Toeplitz三角阵求逆及块Toeplitz三角线性方程组求解的复杂性

In this paper, it is showed that the computational complexity of inversion of block triangular Toeplitz matrix U= (U₀, U₁,…, U_n-1 ) is O (m²nlogn + m³), as well as solution of block triangla r Toeplitz linear systems, where U 's are m×m mat rices. By using this results, we reduce arithmetic operations of division of polynomials from O(nlog²n) to O(nlogn).     

Computational Equivalence Between the Problems of Sorting and Monotone Reconstruction for Random Permutations

In this note,it is shown that the monotone reconstruction problem is equi-valent to that of sorting,in the sense of computational complexity.In particularfrom any given sorting al gorithm A,an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m)time and O(m)space cost morethan that used in A,and vice versa.As a consequence of this result,it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random perm utations is O(nlogn).     

关于多项式回归的复杂性界

多项式回归在回归分析方法中占有特别重要的地位.对具有N组测量数据的M次多项式回归问题,传统算法(例如用Householder变换)需O(N~2M)次算术运算。本文提出一种很简单的快速算法,该算法仅需O(NM)次算术运算。     

RECENT PROGRESS ON SPHERICAL HARMONIC APPROXIMATION MADE BY BNU RESEARCH GROUP ——In memory of Professor Sun Yongsheng

As early as in 1990, Professor Sun Yongsheng, suggested his students at Beijing Normal University to consider research problems on the unit sphere. Under his guidance and encouragement his students started the research on spherical harmonic analysis and approximation. In this paper, we incompletely introduce the main achievements in this area obtained by our group and relative researchers during recent 5 years （2001-2005）. The main topics are： convergence of Cesaro summability, a.e. and strong summability of Fourier-Laplace series; smoothness and K-functionals; Kolmogorov and linear widths.     

A unified approach to certain problems of best local approximation

In this paper we study best local quasi-rational approximation and best local approximation from finite dimensional subspaces of vectorial functions of several variables. Our approach extends and unifies several problems concerning best local multi-point approximation in different norms.     

Boundedness for commutators of multipliers on Hardy type spaces

In this paper, we study the commutators generalized by multipliers and a BMO function. Under some assumptions, we establish its boundedness properties from certain atomic Hardy space Hb^p（R^n） into the Lebesgue space L^p with p 〈 1.     

THE 8~(th) INTERNATIONAL CONGRESS ON INDUSTRIAL AND APPLIED MATHEMATICS

<正>August 10-14,2015Beijing,ChinaThe International Congress on Industrial and Applied Mathematics(ICIAM)is the premier international congress in the field of applied mathematics held every four years under the auspices of the International Council for Industrial and Applied Mathematics.From August 10 to 14,2015,mathematicians,scientists     

Towards Excellence in Science Chinese Academy of Sciences

<正>May 26,2014,Beijing Science is a human enterprise in the pursuit of knowledge.The scientific revolution that occurred in the 17th Century initiated the advances of modern science.The scientific knowledge system created by     

Bounds for the zeros of polynomials

Let P(z)=∑↓j=0↑n ajx^j be a polynomial of degree n. In this paper we prove a more general result which interalia improves upon the bounds of a class of polynomials. We also prove a result which includes some extensions and generalizations of Enestrǒm-Kakeya theorem.     

Boundedness of commutators related to Marcinkiewicz integrals on hardy type spaces

In this paper, the authors study the boundedness of the operator [μΩ, b], the commutator generated by a function b ∈ Lipβ(Rn)(0 ＜β≤ 1) and the Marcinkiewicz integrals μΩ, on the classical Hardy spaces and the Herz-type Hardy spaces in the case Ω∈ Lipα(Sn-1)(0 ＜α≤ 1).     

Jacobi polynomials used to invert the laplace transform

Given the Laplace transform F(s) of a function f(t), we develop a new algorithm to find an approximation to f(t) by the use of the classical Jacobi polynomials. The main contribution of our work is the development of a new and very effective method to determine the coefficients in the finite series expansion that approximation f(t) in terms of Jacobi polynomials. Some numerical examples are illustrated.     

Generalization of the interaction between Haar approximation and polynomial operators to higher order methods

In applications it is useful to compute the local average empirical statistics on u. A very simple relation exists when of a function f（u） of an input u from the local averages are given by a Haar approximation. The question is to know if it holds for higher order approximation methods. To do so, it is necessary to use approximate product operators defined over linear approximation spaces. These products are characterized by a Strang and Fix like condition. An explicit construction of these product operators is exhibited for piecewise polynomial functions, using Hermite interpolation. The averaging relation which holds for the Haar approximation is then recovered when the product is defined by a two point Hermite interpolation.