Uniqueness and stability in an inverse problem for a Poisson’s equation

Consider the Poisson's equation ψ" (x) ＝ -ev-ψ eψ-v-N(x) with the Dirichlet boundary data, and we mainly investigate the inverse problem of determining the unknown function N(x) from a parameter function family. Some uniqueness and stability results in the inverse problem are obtained.     

Symbolic topological sorting with OBDDs

We present a symbolic OBDD algorithm for topological sorting which requires O(log²|V|) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O(log⁴|V|loglog|V|). This is the first true runtime analysis of a symbolic OBDD algorithm for a fundamental graph problem, and it demonstrates that one can hope that the algorithm behaves well for sufficiently structured inputs.     

Local solvability of the cauchy problem of a fifth-order nonlinear dispersive equation

The solvability of the fifth-order nonlinear dispersive equation δtu＋au （δxu）^2＋βδx^3u＋γδx^5u = 0 is studied. By using the approach of Kenig, Ponce and Vega and some Strichartz estimates for the corresponding linear problem,it is proved that if the initial function u0 belongs to H^5（R） and s〉1/4,then the Cauchy problem has a unique solution in C（[-T,T],H^5（R）） for some T〉0.     

Global Existence of Solutions for the Cauchy Problem of the Kawahara Equation with L 2 Initial Data

In this paper we study solvability of the Cauchy problem of the Kawahara equation 偏导dtu ＋ au偏导dzu ＋ β偏导d^3xu ＋γ偏导d^5xu = 0 with L^2 initial data. By working on the Bourgain space X^r,s（R^2） associated with this equation, we prove that the Cauchy problem of the Kawahara equation is locally solvable if initial data belong to H^r（R） and -1 〈 r ≤ 0. This result combined with the energy conservation law of the Kawahara equation yields that global solutions exist if initial data belong to L^2（R）.     

On parallel hashing and integer sorting

The problem of sorting n integers from a restricted range [1…m], where m is a superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m) expected time and O(n) space. (Thus, for m = n^polylog(n) we have an O(n log log n) algorithm.) The algorithm is parallelizable. The resulting parallel algorithm achieves optimal speedup. Some features of the algorithm make us believe that it is relevant for practical applications. A result of independent interest is a parallel hashing technique. The expected construction time is logarithmic using an optimal number of processors, and searching for a value takes O(1) time in the worst case. This technique enables drastic reduction of space requirements for the price of using randomness. Applicability of the technique is demonstrated for the parallel sorting algorithm and for some parallel string matching algorithms. The parallel sorting algorithm is designed for a strong and nonstandard model of parallel computation. Efficient simulations of the strong model on a CRCW PRAM are introduced. One of the simulations even achieves optimal speedup. This is probably the first optimal speedup simulation of a certain kind.     

Forelli-Rudin type theorem in pluriharmonic Bergman spaces with small index

It is proved that the Bergman type operatorT, is a bounded projection from the pluriharmonic Bergman spaceL ^p (B)∩h(B) onto Bergman spaceL ^p (B) ∩ H(B) for 0p 1 ands (p¹-1)(n+1). As an application it is shown that the Gleason’s problem can be solved in Bergman space L^P(B)∩H(B) for 0p 1. Project supported by the National Natural Science Foundation of China (Grant No. 19871081) and the Doctoral Program Foundation of the State Education Commission of China.     

Inverse problem of minimum cuts

Given a networkN = (V,A,c), a sources V, a. sinkt V and somes —t cuts and suppose each element of the capacity vectorc can be changed with a cost proportional to the changes, the inverse problem of minimum cuts we study here is to change the original capacities with the least total cost under restrictions on the changes of the capacities, so that all thoses —t cuts become minimum cuts with respect to the new capacities.In this paper we shall show that the inverse problem of minimum cuts can be directly transformed into a minimum cost circulation problem and therefore can be solved efficiently by strongly polynomial algorithms.The author is grateful to the partial support of the Universities Grant Council of Hong Kong under the grant CITYU #9040189Work partially supported by the National Natural Science Foundation of China     

On a backward problem for fractional diffusion equation with Riemann-Liouville derivative

In the present paper, we study the initial inverse problem (backward problem) for a two-dimensional fractional differential equation with Riemann-Liouville derivative. Our model is considered in the random noise of the given data. We show that our problem is not well-posed in the sense of Hadamard. A truncated method is used to construct an approximate function for the solution (called the regularized solution). Furthermore, the error estimate of the regularized solution in L² and H^τ norms is considered and illustrated by numerical example.     

H m -modified wave operator for nonlinear Hartree equation in space of dimensionn≥2

We consider the scattering problem for the Hartree equation with potential |x|⁻¹ in a space of dimensionn≥2. We prove the existence ofH ^m -modified wave operator for Hartree equation on a dense set of a neighborhood of zero inH ^m (ℝ ⁿ ), meanwhile, we obtain also the global existence for the Cauchy problem of Hartree equation in a space of dimensionn≥2. This project is supported by the National Natural Science Foundation of China, 19601005     

Space-time means and solutions to a class of nonlinear parabolic equations

Cauchy problem and initial boundary value problem for nonlinear parabolic equation inCB([0,T):L ^p ) orL ^q (0,T; L ^p ) type space are considered. Similar to wave equation and dispersive wave equation, the space-time means for linear parabolic equation are shown and a series of nonlinear estimates for some nonlinear functions are obtained by space-time means. By Banach fixed point principle and usual iterative technique a local mild solution of Cauchy problem or IBV problem is constructed for a class of nonlinear parabolic equations inCB([0,T);L ^p orL ^q (0,T; L ^p ) with ϕ(x)∈L ^r . In critical nonlinear case it is also proved thatT can be taken as infinity provided that ||ϕ(x)||_r is sufficiently small, where (p,q,r) is an admissible triple. Project supported by the National Natural Science Foundation of China (Grant No. 19601005).     

Exploiting locality: approximating sorting buffers

The sorting buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity. Whenever a new item arrives it may be moved directly to the service station or stored in the buffer. Also, at any time items can be removed from the buffer and assigned to the service station. Our goal is to give the service station a sequence of items with minimum type transitions. We generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.     

Shadowing and Inverse Shadowing for C^1 Endomorphisms

In this paper, we consider the shadowing and the inverse shadowing properties for C^1 endomorphisms. We show that near a hyperbolic set a C^1 endomorphism has the shadowing property, and a hyperbolic endomorphism has the inverse shadowing property with respect to a class of continuous methods. Moreover, each of these shadowing properties is also ＂uniform＂ with respect to C^1 perturbation.     

The Cauchy Boundary Value Problems on Closed Piecewise Smooth Manifolds in <Emphasis Type="Italic">C</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Suppose that D is a bounded domain with a piecewise C^1 smooth boundary in C^n. Let ψ∈C^1 α(δD). By using the Hadamard principal value of the higher order singular integral and solid angle coefficient method of points on the boundary, we give the Plemelj formula of the higher order singular integral with the Boehner-Martinelli kernel, which has integral density ψ. Moreover, by means of the Plemelj formula and methods of complex partial differential equations, we discuss the corresponding Cauehy boundary value problem with the Boehner-Martinelli kernel on a closed piecewise smooth manifold and obtain its unique branch complex harmonic solution.     

The generalized solution of ill-posed boundary problem

In this paper, we define a kind of new Sobolev spaces, the relative Sobolev spaces Wk,p0(Ω,∑). Then an elliptic partial differential equation of the second order with an ill-posed boundary is discussed. By utilizing the ideal of the generalized inverse of an operator, we introduce the generalized solution of the ill-posed boundary problem. Eventually, the connection between the generalized inverse and the generalized solution is studied. In this way, the non-instability of the minimal normal least square solution of the ill-posed boundary problem is avoided.     

The weighted Fermat-Torricelli problem on a surface and an “inverse” problem

We study the weighted Fermat-Torricelli (w.F-T) problem for geodesic triangles on a C² complete surface and on an Aleksandrov space of curvature bounded above by a real number K and solve an “inverse” problem on a C² complete surface. The solution of the w.F-T problem and the inverse w.F-T problem on a C² complete surface is based on the differentiation of the length of geodesics with respect to the arc length.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

Approximation and eigenvalue extrapolation of Stokes eigenvalue problem by nonconforming finite element methods

In this paper we analyze the stream function-vorticity-pressure method for the Stokes eigenvalue problem. Further, we obtain full order convergence rate of the eigenvalue approximations for the Stokes eigenvalue problem based on asymptotic error expansions for two nonconforming finite elements, Q ₁^rot and EQ ₁^rot. Using the technique of eigenvalue error expansion, the technique of integral identities and the extrapolation method, we can improve the accuracy of the eigenvalue approximations. This project is supported in part by the National Natural Science Foundation of China (10471103) and is subsidized by the National Basic Research Program of China under the grant 2005CB321701.     

An approximation algorithm for sorting by reversals and transpositions

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

Randomized adaptive sorting

Our goal is to design practical sorting algorithms that require time proportional not only to the size of the input but also to the disorder in the input. Such sorting algorithms are said to be adaptive. We introduce randomization to achieve this goal; the first time randomization has used to obtain adaptive sorting algorithms. We investigate three randomized algorithms.

• 1 Randomized Merge Sort, which is expected Runs-optimal;
• 2 Randomized Quicksort, which is Exchange-sensitive, that is, it takes Θ(|X|[1+log(Exc(X)+1)]) time in the expected case; and
• 3 Skip Sort, whichh is Inversions-, Runs-, and Exchhange-optimal.

The three sorting algorithms are simple and practical, in contrast to previous adaptive sorting algorithms that used complex data structures. Moreover, previous claims about the performance of adaptive variants of Quicksort were baed only on simulation results,; our claims are based on a formal analysis. © 1993 John Wiley & Sons. Inc.