Adaptive application of operators in standard representation

Recently adaptive wavelet methods have been developed which can be shown to exhibit an asymptotically optimal accuracy/work balance for a wide class of variational problems including classical elliptic boundary value problems, boundary integral equations as well as certain classes of noncoercive problems such as saddle point problems. A core ingredient of these schemes is the approximate application of the involved operators in standard wavelet representation. Optimal computational complexity could be shown under the assumption that the entries in properly compressed standard representations are known or computable in average at unit cost. In this paper we propose concrete computational strategies and show under which circumstances this assumption is justified in the context of elliptic boundary value problems. Dedicated to Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 41A25, 41A46, 65F99, 65N12, 65N55. This work has been supported in part by the Deutsche Forschungsgemeinschaft SFB 401, the first and third author are supported in part by the European Community's Human Potential Programme under contract HPRN-CT-202-00286 (BREAKING COMPLEXITY). The second author acknowledges the financial support provided through the European Union's Human Potential Programme, under contract HPRN-CT-2002-00285 (HASSIP) and through DFG grant DA 360/4–1.     

He-HCl体系各向异性势及分波散射截面的理论研究

首先用BFW势函数形式拟合了在CCSD(T)/aug-cc-pVQZ理论水平下计算的He-HCl相互作用能数据，获得了He原子与HCl分子相互作用的各向异性势；然后采用CC近似方法计算了He-HCl碰撞体系的微分散射截面和分波散射截面，并总结了分波散射截面的变化规律.结果表明，拟合势不但表达形式简洁，而且较好地描述了He-HCl系统相互作用的各向异性特征；利用碰撞体系分子间势的量子化学从头计算结果，可解决势能参数难以确定的问题.对进一步研究原子与分子碰撞机理有一定参考价值. 关键词： 各向异性势 势能参数 密耦近似 分波散射截面     

Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001     

Error Estimates for Multilevel Approximation Using Polyharmonic Splines

Polyharmonic splines are used to interpolate data in a stationary multilevel iterative refinement scheme. By using such functions the necessary tools are provided to obtain simple pointwise error bounds on the approximation. Linear convergence between levels is shown for regular data on a scaled multiinteger grid, and a multilevel domain decomposition method.     

T-C模型中虚光子过程对光场压缩效应的影响

利用全量子理论,研究非旋波近似下TC模型中受激场的压缩效应.结果表明:非旋波近似下,由于虚光场的影响,Q的演化曲线出现了“小锯齿状”,表现为系统的量子噪声,随着ω和n的增大,量子噪声分别减小和增大,虚光子过程使光场的压缩程度明显加深;研究结果还揭示了原子场耦合系数λ及原子间耦合系数g与光场压缩效应的关系. 关键词： T-C模型 非旋波近似 压缩效应 量子噪声     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

Phonon density of states of ann-component alloy

We have generalized the coherent potential approximation (CPA) of Tripathi and Behera to the case of ann-component alloy. It is seen that then-component CPA density of states reproduces the binary, ternary quartenary alloys etc when the appropriate limits are adopted.     

对称正交反对称矩阵反问题解存在的条件

矩阵反问题和矩阵特征值反问题在科学和工程技术中具有广泛的应用,有关它们的研究已取得了许多进展[1,2].[3]和[4]分别研究了反对称矩阵反问题和双反对称矩阵特征值反问题等.本文研究一类更广泛的对称正交反对称矩阵反问题.用Rn×m（Cn×m）表示n×m实（复）矩阵的全体,ASRn×n表示n阶反对称矩阵的全体,ABSRn×n表示n阶双反对称矩阵的全体,ORn×n表示n阶正交矩阵的全体.A+表示矩阵A的Moore-Penrose广义逆.In表示n阶单位矩阵.ei表示n阶单位矩阵的第i列,Sn=[en,en-1,     

Multiscale kernels

This paper reconstructs multivariate functions from scattered data by a new multiscale technique. The reconstruction uses standard methods of interpolation by positive definite reproducing kernels in Hilbert spaces. But it adopts techniques from wavelet theory and shift-invariant spaces to construct a new class of kernels as multiscale superpositions of shifts and scales of a single compactly supported function φ. This means that the advantages of scaled regular grids are used to construct the kernels, while the advantages of unrestricted scattered data interpolation are maintained after the kernels are constructed. Using such a multiscale kernel, the reconstruction method interpolates at given scattered data. No manipulations of the data (e.g., thinning or separation into subsets of certain scales) are needed. Then, the multiscale structure of the kernel allows to represent the interpolant on regular grids on all scales involved, with cheap evaluation due to the compact support of the function φ, and with a recursive evaluation technique if φ is chosen to be refinable. There also is a wavelet-like data reduction effect, if a suitable thresholding strategy is applied to the coefficients of the interpolant when represented over a scaled grid. Various numerical examples are presented, illustrating the multiresolution and data compression effects.     

Discrete approximation of integral operators

A method to approximate the eigenvalues of linear operators depending on an unknown distribution is introduced and applied to weighted sums of squared normally distributed random variables. This area of application includes the approximation of the asymptotic null distribution of certain degenerated U- and V-statistics.