Structured data-sparse approximation to high order tensors arising from the deterministic Boltzmann equation

We develop efficient data-sparse representations to a class of high order tensors via a block many-fold Kronecker product decomposition. Such a decomposition is based on low separation-rank approximations of the corresponding multivariate generating function. We combine the interpolation and a quadrature-based approximation with hierarchically organised block tensor-product formats. Different matrix and tensor operations in the generalised Kronecker tensor-product format including the Hadamard-type product can be implemented with the low cost. An application to the collision integral from the deterministic Boltzmann equation leads to an asymptotical cost - in the one-dimensional problem size (depending on the model kernel function), which noticeably improves the complexity of the full matrix representation.

     

Krawtchouk多项式的渐近性态

在前人的基础上,对Krawtchouk多项式及其零点的渐近性态进行了研究.首先推导出对于任意固定的u=n/N∈(0,P)或(0,q)Krawtchouk多项式Kn(λN)(其中λ=xN,0<λ<1)的一致有效渐近展开式.然后又得到了它的零点的渐近性态,并对其相应的误差限进行分析.该误差限为o(n-4/3).     

A New Iterative Method for the Computation of the Solutions of Nonlinear Equations

Recently, by Costabile, Gualtieri and Serra (1999), an iterative method was presented for the computation of zeros of C ¹ functions. This method combines the assured convergence of the bisection-like algorithms with a superlinear convergence speed which characterizes Newton-like methods. The order of the method and the cost per iteration is exactly equivalent to the Newton method. In this paper we present a new iterative method for the computation of the zeros of C ¹ functions with the same properties of convergence as the method proposed by Costabile, Gualtieri and Serra (1999) but with order 1+ $\sqrt 2 $ ?2.41 for C ³ functions. Compared with the methods of order 1+ $\sqrt 2 $ presented by Traub (1964), our methods ensure global convergence. Then we consider a generalization of this procedure which gives a class of methods of order (n+ $\sqrt {n^2 + 4} $ )/2, where n is the degree of the approximating polynomial, with one-point iteration functions with memory. Finally a number of numerical tests are performed. The numerical results seem to show that, at least on a set of problems, the new methods work better than the methods proposed, and, therefore, than both the Newton and Alefeld and Potra (1992) methods.     

An Asymptotical $O((k + 1)n^3L)$ Affine Scaling Algorithm for the $P_*(k)$-Matrix Linear Complementarity Problem

Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dinkin-type affine scaling algorithm for solving the $P_*(k)$-matrix linear complementarity problem (LCP). By using high-order correctors technique and rank-one updating, the iteration complexity and the total computational turn out asymptotically $O((\kappa+1)\sqrt{n}L)$ and $O((\kappa+1)n^3L)$ respectively.     

$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法

Mehrotra-type predictor-corrector algorithm,as one of most efficient interior point methods,has become the backbones of most optimization packages.Salahi et al.proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice.We extend their algorithm to P_*（κ）linear complementarity problems.The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ο(（1+4κ）（17+19κ） √（1+2κn）^3/2log[（x⁰）^Ts⁰/ε] worst case iteration complexity bound.An numerical experiment verifies the feasibility of the new algorithm.     

Probabilistic and Average Linear Widths of Sobolev Space with Gaussian Measure in L \infty-Norm

In this paper we investigate the probabilistic linear $(n,\delta)$-widths and $p$-average linear $n$-widths of the Sobolev space $W^r_2$ equipped with the Gaussian measure $\mu$ in the $L_{\infty}$-norm, and determine the asymptotic equalities \begin{eqnarray*} \lambda_{n,\delta}(W^r_2,\mu,L_{\infty}) &\asymp&\frac{\sqrt{\ln (n/\delta)}}{n^{r+(s-1)/2}},\\[3pt] \lambda^{(a)}_n(W^r_2,\mu,L_{\infty})_p &\asymp&\frac{\sqrt{\ln n}}{n^{r+(s-1)/2}}, \qquad 0 < p < \infty. \end{eqnarray*}     

$L^{p}_{[0,1]}$空间M\"{u}ntz有理逼近的Jackson型估计 (英)

设$\Lambda=\{\lambda_{n}\}_{n=1}^{\infty}$为正的实数数列, 且当$n\rightarrow\infty$时, 有$\lambda_{n}\searrow 0$.本文给出了当 $\lambda_{n}\leq Mn^{-\frac{1}{2}},\;n=1,2, \cdots ,$(其中$M>0$为一正常数)时M\"{u}ntz系统$\{x^{\lambda_n}\}$的有理函数在$ L_{[0,1]} ^{p}$空间的逼近速度,主要结论为$R_{n} (f, \Lambda )_{L^{p}}\leq C_M \omega (f, n^{-\frac{1}{2}})_{L^{p}},\;1 \leq p \leq \infty.$     

Chebyshev Spectral Methods and the Lane-Emden Problem

The three-dimensional spherical polytropic Lane-Emden problem is $y_{rr}+(2/r) y_{r} + y^{m}=0, y(0)=1, y_{r}(0)=0$ where $m \in [0, 5]$ is a constant parameter. The domain is $r \in [0, \xi]$ where $\xi$ is the first root of $y(r)$. We recast this as a nonlinear eigenproblem, with three boundary conditions and $\xi$ as the eigenvalue allowing imposition of the extra boundary condition, by making the change of coordinate $x \equiv r/\xi$: $y_{xx}+(2/x) y_{x}+ \xi^{2} y^{m}=0, y(0)=1, y_{x}(0)=0,$ $y(1)=0$. We find that a Newton-Kantorovich iteration always converges from an $m$-independent starting point $y^{(0)}(x)=\cos([\pi/2] x), \xi^{(0)}=3$. We apply a Chebyshev pseudospectral method to discretize $x$. The Lane-Emden equation has branch point singularities at the endpoint $x=1$ whenever $m$ is not an integer; we show that the Chebyshev coefficients are $a_{n} \sim constant/n^{2m+5}$ as $n \rightarrow \infty$. However, a Chebyshev truncation of $N=100$ always gives at least ten decimal places of accuracy — much more accuracy when $m$ is an integer. The numerical algorithm is so simple that the complete code (in Maple) is given as a one page table.     

Stabbing Delaunay Tetrahedralizations

A Delaunay tetrahedralization of $n$ vertices is exhibited for which a straight line can pass through the interiors of $\Theta(n^2)$ tetrahedra. This solves an open problem of Amenta, who asked whether a line can stab more than $O(n)$ tetrahedra. The construction generalizes to higher dimensions: in $d$ dimensions, a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$ Delaunay $d$-simplices. The relationship between a Delaunay triangulation and a convex polytope yields another result: a two-dimensional slice of a $d$-dimensional $n$-vertex polytope can have $\Theta(n^{\lfloor d / 2 \rfloor})$ facets. This last result was first demonstrated by Amenta and Ziegler, but the construction given here is simpler and more intuitive.     

Extrapolation of Nyström Solutions of Boundary Integral Equations on Non-Smooth Domains

The interior Dirichlet problem for Laplace's equation on a plane polygonal region $\Omega$ with boundary $\Gamma$ may be reformulated as a second kind integral equation on $\Gamma$. This equation may be solved by the Nyström method using the composite trapezoidal rule. It is known that if the mesh has $O(n)$ points and is graded appropriately, then $O(1/n^2)$ convergence is obtained for the solution of the integral equation and the associated solution to the Dirichlet problem at any $x\in \Omega$. We present a simple extrapolation scheme which increases these rates of convergence to $O(1/n^4)$ .     

Univariate splines: Equivalence of moduli of smoothness and applications

Several results on equivalence of moduli of smoothness of univariate splines are obtained. For example, it is shown that, for any , , and , the inequality , , is satisfied, where is a piecewise polynomial of degree on a quasi-uniform (i.e., the ratio of lengths of the largest and the smallest intervals is bounded by a constant) partition of an interval. Similar results for Chebyshev partitions and weighted Ditzian-Totik moduli of smoothness are also obtained. These results yield simple new constructions and allow considerable simplification of various known proofs in the area of constrained approximation by polynomials and splines.

     

The Computational Complexity of the Resultant Method for Solving Polynomial Equations

Under an assumption of distribution on zeros of the polynomials, we have given the estimate of computational cost for the resultant method. The result in that, in probability $1-\mu$, the computational cost of the resultant method for finding $ε$-approximations of all zeros is at most $$cd^2(log d+log\frac{1}{\mu}+loglog\frac{1}ε)$$, where the cost is measured by the number of f-evaluations. The estimate of cost can be decreased to $c(d^2logd+d^2log\frac{1}{\mu}+dloglog\frac{1}ε)$ by combining resultant method with parallel quasi-Newton method.     

ROBUST INEXACT ALTERNATING OPTIMIZATION FOR MATRIX COMPLETION WITH OUTLIERS

We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise. We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization, whose objective function consists of an $\ell_1$ norm data fidelity and a rank constraint. To reduce the computational cost per iteration, two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm. The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise. When the noise is severe and the underlying matrix is ill-conditioned, the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.     

线性过程关于大数律的精确渐近性

该文主要讨论的是滑线性过程 $X_k=\sum\limits_{i=-\infty}^\infty a_{i+k}\varepsilon_i$,其中 $\{\varepsilon_i; -\infty$\varphi$ -混合或负相伴随机变量序列,$\{a_i;-\inftyp$, 若 $E|\varepsilon_1|^r<\infty$$\lim_{\epsilon\searrow 0}\epsilon^{2(r-p)/(2-p)}\sum\limits_{n=1}^\infty n^{r/p-2}P\{|S_n|\geq \epsilonn^{1/p}\}=\frac{p}{r-p}E|Z|^{2(r-p)/(2-p)},$ 其中 $Z$ 是服从均值为零,方差为 $\tau^2=\sigma^2\cdot(\sum\limits_{i=-\infty}^\infty a_i)^2$的正态分布.     

Rounding Procedures for the Discrete Version of the Capacitated Economic Order Quantity Problem

The capacitated Economic Order Quantity problem (capacitated EOQ) is a well-known problem where products have to be shipped between two points with a vehicle of given capacity. Each shipment has a fixed cost, independent of the shipped quantity, and an inventory cost is generated in the two points. The problem consists in finding the optimal time between consecutive shipments, which minimizes the total cost. The problem is a capacitated variant of the EOQ problem and has a closed form solution. Since such solution is often irrational, it is often rounded to an integer value. In this paper we investigate the errors which are generated by rounding procedures to integer and powers-of-two values. We show that, although in the worst case a tight general relative error of 2 is generated by all the considered rounding procedures, the procedure which rounds to the best between the lower and upper values (integer or powers-of-two) has a performance of $\frac{1}{2}$ ( $\sqrt 2 + 1/\sqrt 2 $ )≈1.06 on classes of instances of high practical relevance.     

Fixed-charge transportation on a path: optimization, LP formulations and separation

In the fixed-charge transportation problem, the goal is to optimally transport goods from depots to clients when there is a fixed cost associated to transportation or, equivalently, to opening an arc in the underlying bipartite graph. We further motivate its study by showing that it is both a special case and a strong relaxation of the big-bucket multi-item lot-sizing problem, and a generalization of a simple variant of the single-node flow set. This paper is essentially a polyhedral analysis of the polynomially solvable special case in which the associated bipartite graph is a path. We give a $\mathcal O (n^3)$ -time optimization algorithm and a $\mathcal O (n^2)$ -size linear programming extended formulation. We describe a new class of inequalities that we call “path-modular” inequalities. We give two distinct proofs of their validity. The first one is direct and crucially relies on sub- and super-modularity of an associated set function. The second proof is by showing that the projection of the extended linear programming formulations onto the original variable space yields exactly the polyhedron described by the path-modular inequalities. Thus we also show that these inequalities suffice to describe the convex hull of the set of feasible solutions.     

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis-parallel rectangles of various dimensions. (a) We construct a set of $n$ disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least $2n-o(n)$, almost matching an upper bound of dAmore and Franciosa. (b) We establish a similar lower bound of $7n/3-o(n)$ for disjoint rectangles in the plane. (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in $\reals^d$ and disjoint rectangles in $\reals^3$. (d) We derive a worst-case bound of $\Theta(n^{5/3})$ for the size of BSPs of disjoint $2$-rectangles in $4$-space. (e) For disjoint $k$-rectangles in $d$-space, we prove the worst-case bound $\Theta(n^{d/(d-k)})$, for any $k<d/2$; this bound holds for all $k<d$ if the rectangles are allowed to intersect.     

On the solutions of a family of quartic Thue equations

In this paper, we solve a certain family of diophantine equations associated with a family of cyclic quartic number fields. In fact, we prove that for and , with square-free, the Thue equation

has no integral solution except the trivial ones: .

     

A note on the isoperimetric inequality

We show that the sharp integral form on the isoperimetric inequality holds for those orientation-preserving mappings whose Jacobians obey the rule of integration by parts.

     

High-Dimensional Shape Fitting in Linear Time

Let $P$ be a set of $n$ points in $\Re^d$. The {\em radius} of a $k$-dimensional flat ${\cal F}$ with respect to $P$, which we denote by ${\cal RD}({\cal F},P)$, is defined to be $\max_{p \in P} \mathop{\rm dist}({\cal F},p)$, where $\mathop{\rm dist}({\cal F},p)$ denotes the Euclidean distance between $p$ and its projection onto ${\cal F}$. The $k$-flat radius of $P$, which we denote by ${R^{\rm opt}_k}(P)$, is the minimum, over all $k$-dimensional flats ${\cal F}$, of ${\cal RD}({\cal F},P)$. We consider the problem of computing ${R^{\rm opt}_k}(P)$ for a given set of points $P$. We are interested in the high-dimensional case where $d$ is a part of the input and not a constant. This problem is NP-hard even for $k = 1$. We present an algorithm that, given $P$ and a parameter $0 < \eps \leq 1$, returns a $k$-flat ${\cal F}$ such that ${\cal RD}({\cal F},P) \leq (1 + \eps) {R^{\rm opt}_k}(P)$. The algorithm runs in $O(nd C_{\eps,k})$ time, where $C_{\eps,k}$ is a constant that depends only on $\eps$ and $k$. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of $d n^{O(k/\eps^c)}$, where $c$ is an appropriate constant.