NOTES ON POLYNOMIAL LEVELABILITY

We consider the polynomial levelability with respect to approximation algorithms (PLAA).A set A is PLAA if given any approximation algorithm a for A and a polynomial p,there are another approximation algorithm β for A and a polynomial q such that for infinitely many inputs x,a accepts x but has ruuning time greater than p(|x|) and β accepts x within time q(|x|).In this paper,an algorithm a is called an approximation algorithm for A if the symmetric difference A△L(a) is sparse,where L(a) is the set of strings recegnized by a.We prove that all natural NP-complete sets are PLAA unless P=NP and all EXP-complete sets are PLAA.     

A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

A new adaptive subspace minimization three-term conjugate gradient algorithm with nonmonotone line search is introduced and analyzed in this paper.The search directions are computed by minimizing a quadratic approximation of the objective function on special subspaces,and we also proposed an adaptive rule for choosing different searching directions at each iteration.We obtain a significant conclusion that the each choice of the search directions satisfies the sufficient descent condition.With the used nonmonotone line search,we prove that the new algorithm is globally convergent for general nonlinear functions under some mild assumptions.Numerical experiments show that the proposed algorithm is promising for the given test problem set.     

A Remark on Adaptive Decomp osition for Nonlinear Time-frequency Analysis

In recent study the bank of real square integrable functions that have nonlinear phases and admit a well-behaved Hilbert transform has been constructed for adaptive representation of nonlinear signals. We first show in this paper that the available basic functions are adequate for establishing an ideal adaptive decomposi-tion algorithm. However, we also point out that the best approximation algorithm, which is a common strategy in decomposing a function into a sum of functions in a prescribed class of basis functions, should not be considered as a candidate for the ideal algorithm.     

COMPUTING THE NEAREST BISYMMETRIC POSITIVE SEMIDEFINITE MATRIX UNDER THE SPECTRAL RESTRICTION

Let A and C denote real n × n matrices. Given real n-vectors x1, ... ,xm, m ≤ n, and a set of numbers L = {λ1,λ2,... ,λm}. We describe (I) the set (?) of all real n × n bisymmetric positive seidefinite matrices A such that Axi is the "best" approximate to λixi, i = 1,2,...,m in Frobenius norm and (II) the Y in set (?) which minimize Frobenius norm of ||C - Y||.An existence theorem of the solutions for Problem I and Problem II is given and the general expression of solutions for Problem I is derived. Some sufficient conditions under which Problem I and Problem II have an explicit solution is provided. A numerical algorithm of the solution for Problem II has been presented.     

A Novel Genetic Algorithm for Global Optimization

This paper presents a novel genetic algorithm for globally solving un-constraint optimization problem.In this algorithm,a new real coded crossover operator is proposed firstly.Furthermore,for improving the convergence speed and the searching ability of our algorithm,the good point set theory rather than random selection is used to generate the initial population,and the chaotic search operator is adopted in the best solution of the current iteration.The experimental results tested on numerical benchmark functions show that this algorithm has excellent solution quality and convergence characteristics,and performs better than some algorithms.     

Nagata-like theorems for almost Prüfer v-multiplication domains

Let D be an integral domain and X an indeterminate over D . We show that if S is an almost splitting set of an integral domain D , then D is an APVMD if and only if both DS and DN(S) are APVMDs. We also prove that if {Dα}α∈I is a collection of quotient rings of D such that D=∩α∈IDα has finite character (that is, each nonzero d∈D is a unit in almost all Dα) and each of Dα is an APVMD, then D is an APVMD. Using these results, we give several Nagata-like theorems for APVMDs.     

The Error in the Approximation

In applying any numerical method such as the bisection method to determine a root, it is important to realize that the best we can usually achieve is an approximation ofthe exact root. At each iteration of the method,we obtain a better estimate of the root. Thus it becomes desirable that we be able to estimate how accurate the approximation is at each stage so that we know when to stop the process.With the bisection method,suppose we know that there is a root in some interval [a,b], where a and b are successive integers, say 2 and 3. If we select the midpoint M1 of this interval, then it is obvious that the root R is     

A theoretical analysis on efficiency of some Newton-PCG methods

In this paper, we study the efficiency issue of inexact Newton-type methods for smooth unconstrained optimization problems under standard assumptions from theoretical point of view by discussing a concrete Newton-PCG algorithm. In order to compare the algorithm with Newton's method, a ratio between the measures of their approximate efficiencies is investigated. Under mild conditions, it is shown that first, this ratio is larger than 1, which implies that the Newton-PCG algorithm is more efficient than Newton's method, and second, this ratio increases when the dimension n of the problem increases and tends to infinity at least at a rate In n/In 2 when n→∞, which implies that in theory the Newton-PCG algorithm is much more efficient for middle- and large-scale problems. These theoretical results are also supported by our preliminary numerical experiments.     

Three-space problems for the bounded compact approximation property

In this paper, the notion of the bounded compact approximation property (BCAP) of a pair [Banach space and its subspace] is used to prove that if X is a closed subspace of L∞ with the BCAP, then L∞/X has the BCAP. We also show that X* has the λ-BCAP with conjugate operators if and only if the pair (X, Y) has the λ-BCAP for each finite codimensional subspace Y∈X. Let M be a closed subspace of X such that M⊥ is complemented in X*. If X has the (bounded) approximation property of order p, then M has the (bounded) approximation property of order p.     

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_ij) with \begin{align*}\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0\end{align*} and a (small) k × k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁,…,S_k} of {1,…n} which maximizes \begin{align*}\sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}\end{align*}. We design a polynomial time approximation algorithm that achieves an approximation ratio of \begin{align*}\frac{R(B)^2}{C(B)}\end{align*}, where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_ij = 〈v_i,v_j〉 is the Gram matrix representation of B for some \begin{align*}v_1,\ldots,v_k\in \mathbb{R}^k\end{align*} then R(B) is the minimum radius of a Euclidean ball containing the points {v₁,…,v_k}. The parameter C(B) is defined as the maximum over all measurable partitions {A₁,…,A_k} of \begin{align*}\mathbb{R}^{k-1}\end{align*} of the quantity \begin{align*}\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle\end{align*}, where for i∈{1,…,k} the vector \begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*} is the Gaussian moment of A_i, i.e., \begin{align*}z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx\end{align*}. We also show that for every ε > 0, achieving an approximation guarantee of \begin{align*}(1-\varepsilon)\frac{R(B)^2}{C(B)}\end{align*} is Unique Games hard. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Homogeneous expansions of normalized biholomorphic convex mappings overB P

The power series expansions of normalized biholomorphic convex mappings on the Reinhardt domain are studied. It is proved that the first (k+1) terms of the expansions of the jth componentf j of such a mapf depend only onz _j , for 1 ⩽j⩽n, wherek is the natural number that satisfiesk < ρ ⩽k +I. Whenp→ ∞, this gives the result on the unit polydisc obtained by Suffridge in 1970. Project supported in part by the National Natural Science Foundation of China.     

An interpolation theorem for proper holomorphic embeddings

Given a Stein manifold x of dimension n > 1, a discrete sequence , and a discrete sequence where , there exists a proper holomorphic embedding satisfying f(a _j ) = b _j for every j = 1,2,... Forstnerič and Prezelj supported by grants P1-0291 and J1-6173, Republic of Slovenia. Kutzschebauch supported by Schweizerische National fonds grant 200021-107477/1. Ivarsson supported by The Wenner-Gren Foundations.     

Irregular Wavelet Frames and Gabor Frames

Given g { l^\fracn2 g( l_j x - kb ) }_jezjezⁿ ,where  l_j \left\{ {\lambda ^{\frac{n}{2}} g\left( {\lambda _j x - kb} \right)} \right\}_{j\varepsilon zj\varepsilon z^n } ,where\;\lambda _j > 0 and b > 0. Sufficient conditions for the wavelet system to constitute a frame for L ²(R ⁿ ) are given. For a class of functions g{ e^{zrib( j,x )} g( x - l_k ) }_{jezⁿ ,kez}\left\{ {e^{zrib\left( {j,x} \right)} g\left( {x - \lambda _k } \right)} \right\}_{j\varepsilon z^n ,k\varepsilon z} to be a frame.     

Pointwise estimates for Lagrange interpolation polynomials

Let f ∈ C[?1, 1]. Let the approximation rate of Lagrange interpolation polynomial of f based on the nodes $ \left\{ {\cos \frac{{2k - 1}} {{2n}}\pi } \right\} \cup \{ - 1,1\} $ be Δ _{n + 2}(f, x). In this paper we study the estimate of Δ _{n + 2}(f,x), that keeps the interpolation property. As a result we prove that $$ \Delta _{n + 2} (f,x) = \mathcal{O}(1)\left\{ {\omega \left( {f,\frac{{\sqrt {1 - x^2 } }} {n}} \right)\left| {T_n (x)} \right|\ln (n + 1) + \omega \left( {f,\frac{{\sqrt {1 - x^2 } }} {n}\left| {T_n (x)} \right|} \right)} \right\}, $$ where T _n (x) = cos (n arccos x) is the Chebeyshev polynomial of first kind. Also, if f ∈ C ^r [?1, 1] with r ≧ 1, then $$ \Delta _{n + 2} (f,x) = \mathcal{O}(1)\left\{ {\frac{{\sqrt {1 - x^2 } }} {{n^r }}\left| {T_n (x)} \right|\omega \left( {f^{(r)} ,\frac{{\sqrt {1 - x^2 } }} {n}} \right)\left( {\left( {\sqrt {1 - x^2 } + \frac{1} {n}} \right)^{r - 1} \ln (n + 1) + 1} \right)} \right\}. $$      

The Asymptotics of the Two-Dimensional Wave Equation for a General Multi-Connected Vibrating Membrane with Piecewise Smooth Robin Boundary Conditions

The asymptotic expansion for small |t| of the trace of the wave kernel ∧↑μ(t) =∑v=1^∞exp(-it μv^1/2), where i= √-1 and {μv}v=1^∞ are the eigenvalues of the negative Laplacian -△=-∑β=1^2(δ/δx^β)^2 in the (x^1, x^2)-plane, is studied for a multi-connected vibrating membrane Ω in R^2 surrounded by simply connected bounded domains Ωj with smooth boundaries δΩj(j=1,...,n), where a finite number of piecewise smooth Robin boundary conditions on the piecewise smooth components Гi(i=1 κj-1,...,κj) of the boundaries δΩj are considered, such that δΩj=∪i=1 κj-1^κj Гi and κ0=0. The basic problem is to extract information on the geometry of Ω using the wave equation approach. Some geometric quantities of Ω (e.g. the area of Ω, the total lengths of its boundary, the curvature of its boundary, the number of the holes of Ω, etc.) are determined from the asymptotic expansion of the trace of the wave kernel ∧↑μ(t) for small |t|.     

The lattice points of ann-dimensional tetrahedron

We show that the number of orderedm-tuples of points on the integer lattice, inside or on then-dimensional tetrahedron bounded by the hyperplanesX ₁=0,X ₂=0, ...,X _n=0 andw ₁ X ₁+w ₂ X _n+...+w _n X_n=X, with the property that, for eachj, no more thank such points have non-zerojth ordinate, is asymptotically

Free membrane eigenvalues

For a simply connected and normalized domain D in the plane it was proven by Pólya and Schiffer in 1954 for the fixed membrane eigenvalues

The view-obstruction problem for 3-dimensional spheres

LetC be ann-dimensional sphere with diameter 1 and center at the origin inE ⁿ . The view-obstruction problem forn-dimensional spheres is to determine a constant ν(n) to be the lower bound of those α for which any half-lineL, given byx _i =a _i t (i=1,2,...,n) where parametert≥0 anda _i (i=1,2,...,n) are positive real numbers, intersects

On the Crank-Nicolson scheme once again

Let (t_j)_{j ? \mathbbN}{\left(\tau_j\right)_{j\in\mathbb{N}}} be a sequence of strictly positive real numbers, and let A be the generator of a bounded analytic semigroup in a Banach space X. Put A_n=?_j=1ⁿ(I+\frac12 t_jA) (I-\frac12 t_jA)^-1{A_n=\prod_{j=1}^n\left(I+\frac{1}{2} \tau_jA\right) \left(I-\frac{1}{2} \tau_jA\right)^{-1}}, and let x ? X{x\in X}. Define the sequence (x_n)_{n ? \mathbbN} ì X{\left(x_n\right)_{n\in\mathbb{N}}\subset X} by the Crank–Nicolson scheme: x _n  = A _n x. In this paper, it is proved that the Crank–Nicolson scheme is stable in the sense that sup_{n ? \mathbbN}||A_nx|| < ￥{\sup_{n\in\mathbb{N}}\left\Vert A_nx\right\Vert<\infty}. Some convergence results are also given.