Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

An existence and uniqueness principle for a nonlinear version of the Lebowitz‐Rubinow model with infinite maximum cycle length

The present article deals with existence and uniqueness results for a nonlinear evolution initial‐boundary value problem, which originates in an age‐structured cell population model introduced by Lebowitz and Rubinow (1974) describing the growth of a cell population. Cells of this population are distinguished by age a and cycle length l. In our framework, daughter and mother cells are related by a general reproduction rule that covers all known biological ones. In this paper, the cycle length l is allowed to be infinite. This hypothesis introduces some mathematical difficulties. We consider both local and nonlocal boundary conditions.     

SQP algorithms for solving Toeplitz matrix approximation problem

Given an n × n matrix F, we find the nearest symmetric positive semi‐definite Toeplitz matrix T to F. The problem is formulated as a non‐linear minimization problem with positive semi‐definite Toeplitz matrix as constraints. Then a computational framework is given. An algorithm with rapid convergence is obtained by l₁ Sequential Quadratic Programming (SQP) method. Copyright © 2002 John Wiley & Sons, Ltd.     

On the existence of bounded noncontinuable solutions

This paper presents necessary and sufficient conditions for an n ‐th order differential equation to have a non‐continuable solution with finite limits of its derivatives up to the order l at the right‐hand end point of the interval of its definition, l ≤ n – 2 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An improvement and an extension of the Elzinga & Hearn's algorithm to the 1-center problem in ℝn withl 2b-normswithl 2b-norms

Summary In this paper we deal with the 1-center problem in ℝⁿ when the distance is measured by anyl _2b-norm. This type of norm generalizes the Euclidean norm (l ₂-norm) and can be used to estimate road distances or travel times in Locational Analysis, and to measure dissimilarities between data in Cluster Analysis. The problem is to find the smallestb-ellipsoid containing a given finite setA of points in ℝⁿ, which generalizes the one of finding the smallest sphere containingA (1-center problem with thel ₂-norm). We show that this problem has a unique optimal solution. For thel ₂-norm, we use the Elzinga-Hearn algorithm. New starting rules are proposed to initialize and to improve the algorithm. On the other hand, the Elzinga-Hearn algorithm is extended to solve the problem withl _2b-norms. Computational results are given for six differentl _2b-norms, when these new starting rules are used in order to show which is the best starting rule. Problems of up to 5.000 points in ℝⁿ,n=2,4,6,8 and 10, are solved in a few seconds.     

The asymptotic distribution of long cycles in random regular graphs

The asymptotic distribution of the number of cycles of length l in a random r‐regular graph is determined. The length of the cycles is defined as a function of the number of vertices n, thus l=l(n), and the length satisfies l(n)→∞ as n→∞. The limiting distribution turns out to depend on whether l(n)/n→0 or l(n)/n→q, 0<q<1 as n→∞. In the first case the limit distribution is a weighted sum of Poisson variables while in the other case the limit distribution is similar to the limit distribution of Hamiltonian cycles in a random r‐regular graph. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15: 43–92, 1999     

The Poincaré center‐focus problem for a class of higher order polynomial differential systems

In this paper, I have proved that for a class of polynomial differential systems of degree n + 1 (where n is an arbitrary positive integer), the composition conjecture is true. I give the sufficient and necessary conditions for these differential systems to have a center at origin point by using a different method from the previous references. By this, I can obtain all the focal values of these systems for an arbitrary n, and their expressions are succinct and beautiful. I believe that the idea and method of this article can be used to solve the center‐focus problem of more high‐order polynomial differential systems.     

Eigenfunctions and Very Singular Similarity Solutions of Odd‐Order Nonlinear Dispersion PDEs: Toward a “Nonlinear Airy Function” and Others

Asymptotic properties of nonlinear dispersion equations (1) with fixed exponents n > 0 and p > n+ 1 , and their (2k+ 1) th‐order analogies are studied. The global in time similarity solutions, which lead to “nonlinear eigenfunctions” of the rescaled ordinary differential equations (ODEs), are constructed. The basic mathematical tools include a “homotopy‐deformation” approach, where the limit in the first equation in ( 1 ) turns out to be fruitful. At n= 0 the problem is reduced to the linear dispersion one: whose oscillatory fundamental solution via Airy’s classic function has been known since the nineteenth century. The corresponding Hermitian linear non‐self‐adjoint spectral theory giving a complete countable family of eigenfunctions was developed earlier in [ 1 ]. Various other nonlinear operator and numerical methods for ( 1 ) are also applied. As a key alternative, the “super‐nonlinear” limit , with the limit partial differential equation (PDE) admitting three almost “algebraically explicit” nonlinear eigenfunctions, is performed. For the second equation in ( 1 ), very singular similarity solutions (VSSs) are constructed. In particular, a “nonlinear bifurcation” phenomenon at critical values {p=p_l(n)}_l≥0 of the absorption exponents is discussed.     

The unramified computation of Rankin-Selberg integrals for SO2l × GLn

Let SO _2l be the special orthogonal group, either split or quasi-split over a number field, and 1 < l < n. We compute the local integral, where data are unramified, derived from the global Rankin-Selberg construction for SO _2l × GL _n . In the general case, the local integral is difficult to compute directly, so instead it is transformed to an integral related to a construction for SO _2n+1×GL _n , which carries a Bessel model on SO _2n+1. For the quasisplit case, when l = n − 1 we are able to compute the local integral, by a modification of our recently introduced approach using invariant theory. This leads to another proof of our result for 1 < l < n, as well as a new proof of a known result regarding the unramified Bessel function.     

A new technique of using homotopy analysis method for solving high‐order nonlinear differential equations

In this paper, a new technique of homotopy analysis method (HAM) is proposed for solving high‐order nonlinear initial value problems. This method improves the convergence of the series solution, eliminates the unneeded terms and reduces time consuming in the standard homotopy analysis method (HAM) by transform the nth‐order nonlinear differential equation to a system of n first‐order equations. Second‐ and third‐ order problems are solved as illustration examples of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

Canonical dual least square method for solving general nonlinear systems of quadratic equations

This paper presents a canonical dual approach for solving general nonlinear algebraic systems. By using least square method, the nonlinear system of m-quadratic equations in n-dimensional space is first formulated as a nonconvex optimization problem. We then proved that, by the canonical duality theory developed by the second author, this nonconvex problem is equivalent to a concave maximization problem in ℝ ^m , which can be solved easily by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.     

Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u⁴n) and the p-partition problem can be solved in time O(p²u⁴n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.     

Low‐rank approximation of tensors via sparse optimization

The goal of this paper is to find a low‐rank approximation for a given nth tensor. Specifically, we give a computable strategy on calculating the rank of a given tensor, based on approximating the solution to an NP‐hard problem. In this paper, we formulate a sparse optimization problem via an l₁‐regularization to find a low‐rank approximation of tensors. To solve this sparse optimization problem, we propose a rescaling algorithm of the proximal alternating minimization and study the theoretical convergence of this algorithm. Furthermore, we discuss the probabilistic consistency of the sparsity result and suggest a way to choose the regularization parameter for practical computation. In the simulation experiments, the performance of our algorithm supports that our method provides an efficient estimate on the number of rank‐one tensor components in a given tensor. Moreover, this algorithm is also applied to surveillance videos for low‐rank approximation.     

The evolution to a steady state for a porous medium model

An initial boundary value problem is considered for a nonlinear diffusion equation, the diffusivity being a function of the dependent variable. Dirichlet boundary conditions, independent of time, are considered and positive solutions are assumed. This paper is mainly concerned with the rate of convergence, in time, of the unsteady to the steady state. This is done by obtaining an upper estimate for a positive-definite, integral measure of the perturbation (i.e., unsteady-steady state) using differential inequality techniques.A previous result is recalled where the diffusivity k(τ)=τn (n being a positive constant) appropriate to mass transport, or filtration, in a porous medium. The present paper treats an alternative model, sharing some of the characteristics of the previous one: k(τ)=eτ−1, τ being non-negative.The paper concludes by considering a “backwards in time” initial boundary value problem for the perturbation (amenable to the same techniques) and establishes that the solution ceases to exist beyond a critical, computable time.     

Dirichlet duality and the nonlinear Dirichlet problem

We study the Dirichlet problem for fully nonlinear, degenerate elliptic equations of the form F (Hess u) = 0 on a smoothly bounded domain Ω ? ?ⁿ. In our approach the equation is replaced by a subset F ? Sym²(?ⁿ) of the symmetric n × n matrices with ?F ? { F = 0}. We establish the existence and uniqueness of continuous solutions under an explicit geometric “F‐convexity” assumption on the boundary ?Ω. We also study the topological structure of F‐convex domains and prove a theorem of Andreotti‐Frankel type. Two key ingredients in the analysis are the use of “subaffine functions” and “Dirichlet duality.” Associated to F is a Dirichlet dual set F? that gives a dual Dirichlet problem. This pairing is a true duality in that the dual of F? is F, and in the analysis the roles of F and F? are interchangeable. The duality also clarifies many features of the problem including the appropriate conditions on the boundary. Many interesting examples are covered by these results including: all branches of the homogeneous Monge‐Ampère equation over ?, ?, and ?; equations appearing naturally in calibrated geometry, Lagrangian geometry, and p‐convex Riemannian geometry; and all branches of the special Lagrangian potential equation. © 2008 Wiley Periodicals, Inc.     

Design of observers for nonlinear systems with H ∞ performance analysis

This paper investigates the problem of observer design for nonlinear systems. By using differential mean value theorem, which allows transforming a nonlinear error dynamics into a linear parameter varying system, and based on Lyapunov stability theory, an approach of observer design for a class of nonlinear systems with time‐delay is proposed. The sufficient conditions, which guarantee the estimation error to asymptotically converge to zero, are given. Furthermore, an adaptive observer design for a class of nonlinear system with unknown parameter is considered. A method of H _∞ adaptive observer design is presented for this class of nonlinear systems; the sufficient conditions that guarantee the convergence of estimation error and the computing method for observer gain matrix are given. Finally, an example is given to show the effectiveness of our proposed approaches. Copyright © 2013 John Wiley & Sons, Ltd.     

Existence and uniqueness for a nonlinear inverse reaction‐diffusion problem with a nonlinear source in higher dimensions

This paper analyzes the existence and the uniqueness problem for an n‐dimensional nonlinear inverse reaction‐diffusion problem with a nonlinear source. A transformation is used to obtain a new inverse coefficient problem. Then, a parabolic differential operator L_λ is defined to establish the relation between the solution of L_λ = 0 and the new inverse problem. Following this, it is shown that the inverse problem has at least one solution in the class of admissible coefficients. Furthermore, it is proved that this solution is the unique solution of the undertaken inverse problem. A numerical example is given to illustrate ill‐posedness of the inverse problem. Copyright © 2013 John Wiley & Sons, Ltd.     

Color critical hypergraphs with many edges

We show that for all k ≥ 3, r > l ≥ 2 there exists constant c = c(k, r, l) such that for large enough n there exists a k‐color‐critical r‐uniform hypergraph on less than n vertices, having more than cn^l edges, and having no l‐set of vertices occuring in more than one edge. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 56–74, 2006     

Determination of a control function in three‐dimensional parabolic equations by Legendre pseudospectral method

A Legendre pseudospectral method is proposed for solving approximately an inverse problem of determining an unknown control parameter p(t) which is the coefficient of the solution u(x, y, z, t) in a diffusion equation in a three‐dimensional region. The diffusion equation is to be solved subject to suitably prescribed initial‐boundary conditions. The presence of the unknown coefficient p(t) requires an extra condition. This extra condition considered as the integral overspecification over the spacial domain. For discretizing the problem, after homogenization of the boundary conditions, we apply the Legendre pseudospectral method in a matrix based manner. As a results a system of nonlinear differential algebraic equations is generated. Then by using suitable transformation, the problem will be converted to a homogeneous time varying system of linear ordinary differential equations. Also a pseudospectral method for efficient solving of the resulted system of ordinary differential equations is proposed. The solution of this system gives the approximation to values of u and p. The matrix based structure of the present method makes it easy to implement. Numerical experiments are presented to demonstrate the accuracy and the efficiency of the proposed computational procedure. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 74‐93, 2012     

The n‐order rogue waves of Fokas–Lenells equation

Considering certain terms of the next asymptotic order beyond the nonlinear Schrödinger equation, the Fokas–Lenells (FL) equation governed by the FL system arises as a model for nonlinear pulse propagation in optical fibers. The expressions of the q^[n] and r^[n] in the FL system are generated by the n‐fold Darboux transformation (DT), each element of the matrix is a 2 × 2 matrix, expressed by a ratio of (2n + 1) × (2n + 1) determinant and 2n × 2n determinant of eigenfunctions. Further, a Taylor series expansion about the n‐order breather solutions q^[n] generated using by DT and assuming periodic seed solutions under reduction can generate the n‐order rogue waves of the FL equation explicitly with 2n + 3 free parameters. Copyright © 2014 John Wiley & Sons, Ltd.