On the number of segments needed in a piecewise linear approximation

The introduction of high-speed circuits to realize an arithmetic function f as a piecewise linear approximation has created a need to understand how the number of segments depends on the interval a≤x≤b and the desired approximation error ε. For the case of optimum non-uniform segments, we show that the number of segments is given as , (ε→0⁺), where . Experimental data shows that this approximation is close to the exact number of segments for a set of 14 benchmark functions. We also show that, if the segments have the same width (to reduce circuit complexity), then the number of segments is given by , (ε→0⁺), where .     

内积空间上最小二乘形式的矩阵Pade-型逼近

当矩阵幂级数的展开式的系数产生微小摄动时,矩阵Padé-型逼近解往往变化很大.本文在矩阵Padé-型逼近研究的基础上,受Brezinski的启发,借助于误差公式和最小二乘法构造了一种稳定性和精确度均有所提高的矩阵Padé-型逼近的新方法,即最小二乘形式的矩阵Padé-型逼近(LSMPTA),并给出了LSMPTA完整的分子和分母行列式表达式.最后,通过数值实例说明了这一方法的有效性.     

Polynomial approximation, local polynomial convexity, and degenerate CR singularities

We begin with the following question: given a closed disc and a complex-valued function , is the uniform algebra on generated by z and F equal to ? When F∈C¹(D), this question is complicated by the presence of points in the surface that have complex tangents. Such points are called CR singularities. Let p∈S be a CR singularity at which the order of contact of the tangent plane with S is greater than 2; i.e. a degenerate CR singularity. We provide sufficient conditions for S to be locally polynomially convex at the degenerate singularity p. This is useful because it is essential to know whether S is locally polynomially convex at a CR singularity in order to answer the initial question. To this end, we also present a general theorem on the uniform algebra generated by z and F, which we use in our investigations. This result may be of independent interest because it is applicable even to non-smooth, complex-valued F.     

关于I.Joo的一个插值过程

研究I.Joo引入的在区间[0,＋∞）上定义的一个插值过程R_n（f,x）.逼近可微函数f（x）的阶以及同时逼近问题.     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

Kronecker product approximation preconditioners for convection–diffusion model problems

We consider the iterative solution of linear systems arising from four convection–diffusion model problems: scalar convection–diffusion problem, Stokes problem, Oseen problem and Navier–Stokes problem. We design preconditioners for these model problems that are based on Kronecker product approximations (KPAs). For this we first identify explicit Kronecker product structure of the coefficient matrices, in particular for the convection term. For the latter three model cases, the coefficient matrices have a 2 × 2 block structure, where each block is a Kronecker product or a summation of several Kronecker products. We then use this structure to design a block diagonal preconditioner, a block triangular preconditioner and a constraint preconditioner. Numerical experiments show the efficiency of the three KPA preconditioners, and in particular of the constraint preconditioner that usually outperforms the other two. This can be explained by the relationship that exists between these three preconditioners: the constraint preconditioner can be regarded as a modification of the block triangular preconditioner, which at its turn is a modification of the block diagonal preconditioner based on the cell Reynolds number. Copyright © 2009 John Wiley & Sons, Ltd.     

Cross approximation in tensor electron density computations

We propose new tensor approximation algorithms for certain discrete functions related with Hartree–Fock/Kohn–Sham equations. Given a canonical tensor representation for the electron density function (for example, produced by quantum chemistry packages such as MOLPRO), we obtain its Tucker approximation with much fewer parameters than the input data and the Tucker approximation for the cubic root of this function, which is part of the Kohn–Sham exchange operator. The key idea is in the fast and accurate prefiltering of possibly large‐scale factors of the canonical tensor input. The new algorithms are based on the incomplete cross approximation method applied to matrices and tensors of order 3 and outperform other tools for the same purpose. First, we show that the cross approximation method is robust and much faster than the singular value decomposition‐based approach. As a consequence, it becomes possible to increase the resolution of grid and the complexity of molecules that can be handled by the Hartree–Fock chemical models. Second, we propose a new fast approximation method for f^1/3(x, y, z), based on the factor prefiltering method for f(x, y, z) and certain mimic approximation hypothesis. Third, we conclude that the Tucker format has advantages in the storage and computation time compared with the ubiquitous canonical format. Copyright © 2009 John Wiley & Sons, Ltd.     

Algebraic analysis of two‐grid methods: The nonsymmetric case

Two‐grid methods constitute the building blocks of multigrid methods, which are among the most efficient solution techniques for solving large sparse systems of linear equations. In this paper, an analysis is developed that does not require any symmetry property. Several equivalent expressions are provided that characterize all eigenvalues of the iteration matrix. In the symmetric positive‐definite (SPD) case, these expressions reproduce the sharp two‐grid convergence estimate obtained by Falgout, Vassilevski and Zikatanov (Numer. Linear Algebra Appl. 2005; 12 :471–494), and also previous algebraic bounds, which can be seen as corollaries of this estimate. These results allow to measure the convergence by checking ‘approximation properties’. In this work, proper extensions of the latter to the nonsymmetric case are presented. Sometimes approximation properties for the SPD case are summarized in loose terms; e.g.: Interpolation must be able to approximate an eigenvector with error bound proportional to the size of the eigenvalue (SIAM J. Sci. Comp. 2000; 22 :1570–1592). It is shown that this can be applied to nonsymmetric problems too, understanding ‘size’ as ‘modulus’. Eventually, an analysis is developed, for the nonsymmetric case, of the theoretical foundations of ‘compatible relaxation’, according to which a Fine/Coarse partitioning may be checked and possibly improved. Copyright © 2009 John Wiley & Sons, Ltd.     

Bootstrap approximation of wavelet estimates in a semiparametric regression model

The inference for the parameters in a semiparametric regression model is studied by using the wavelet and the bootstrap methods. The bootstrap statistics are constructed by using Efron＇s resampling technique, and the strong uniform convergence of the bootstrap approximation is proved. Our results can be used to construct the large sample confidence intervals for the parameters of interest. A simulation study is conducted to evaluate the finite-sample performance of the bootstrap method and to compare it with the normal approximation-based method.