A two‐grid method for mixed finite‐element solution of reaction‐diffusion equations

We present a scheme for solving two‐dimensional, nonlinear reaction‐diffusion equations, using a mixed finite‐element method. To linearize the mixed‐method equations, we use a two grid scheme that relegates all the Newton‐like iterations to a grid Δ_H much coarser than the original one Δ_h, with no loss in order of accuracy so long as the mesh sizes obey . The use of a multigrid‐based solver for the indefinite linear systems that arise at each coarse‐grid iteration, as well as for the similar system that arises on the fine grid, allows for even greater efficiency. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 317–332, 1999     

Solutions of symmetry‐constrained least‐squares problems

In this paper, two new matrix‐form iterative methods are presented to solve the least‐squares problem: and matrix nearness problem: where matrices and are given; ??₁ and ??₂ are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and S_XY is the solution pair set of the minimum residual problem. These new matrix‐form iterative methods have also faster convergence rate and higher accuracy than the matrix‐form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13 : 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix‐form iterative methods. Some numerical examples illustrate the efficiency of the new matrix‐form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd.     

Asymptotics of solutions for sub critical non‐convective type equations

We study the Cauchy problem for non‐linear dissipative evolution equations (1) where ?? is the linear pseudodifferential operator and the non‐linearity is a quadratic pseudodifferential operator (2) û ≡ ?_x→ξ u is the Fourier transformation. We consider non‐convective type non‐linearity, that is we suppose that a(t,0,y) ≠ 0. Let the initial data , are sufficiently small and have a non‐zero total mass , where is the weighted Sobolev space. Then we give the main term of the large time asymptotics of solutions in the sub critical case. Copyright © 2004 John Wiley & Sons, Ltd.     

Two‐grid mixed finite‐element methods for nonlinear Schrödinger equations

Two‐grid mixed finite element schemes are developed for solving both steady state and unsteady state nonlinear Schrödinger equations. The schemes use discretizations based on a mixed finite‐element method. The two‐grid approach yields iterative procedures for solving the nonlinear discrete equations. The idea is to relegate all of the Newton‐like iterations to grids much coarser than the final one, with no loss in order of accuracy. Numerical tests are performed. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 63‐73, 2012     

The quasi‐randomness of hypergraph cut properties

Let satisfy and suppose a k‐uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets of sizes , the number of edges intersecting is (asymptotically) the number one would expect to find in a random k‐uniform hypergraph. Can we then infer that H is quasi‐random? We show that the answer is negative if and only if . This resolves an open problem raised in 1991 by Chung and Graham [J AMS 4 (1991), 151–196]. While hypergraphs satisfying the property corresponding to are not necessarily quasi‐random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi‐random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Incomplete Self‐Similar Blow‐Up in a Semilinear Fourth‐Order Reaction‐Diffusion Equation

Blow‐up behavior for the fourth‐order semilinear reaction‐diffusion equation (1) is studied. For the classic semilinear heat equation from combustion theory (2) various blow‐up patterns were investigated since 1970s, while the case of higher‐order diffusion was studied much less. Blow‐up self‐similar solutions of (1) of the form are constructed. These are shown to admit global similarity extensions for t > T : The continuity at t = T is preserved in the sense that This is in a striking difference with blow‐up for (2) , which is known to be always complete in the sense that the minimal (proper) extension beyond blow‐up is u(x, t) ≡+∞ for t > T . Difficult fourth‐order dynamical systems for extension pairs {f(y), F(y)} are studied by a combination of various analytic, formal, and numerical methods. Other nonsimilarity patterns for (1) with nongeneric complete blow‐up are also discussed.     

Two‐Grid method for nonlinear parabolic equations by expanded mixed finite element methods

In this article, we develop a two‐grid algorithm for nonlinear reaction diffusion equation (with nonlinear compressibility coefficient) discretized by expanded mixed finite element method. The key point is to use two‐grid scheme to linearize the nonlinear term in the equations. The main procedure of the algorithm is solving a small‐scaled nonlinear equations on the coarse grid and dealing with a linearized system on the fine space using the Newton iteration with the coarse grid solution. Error estimation to the expanded mixed finite element solution is analyzed in detail. We also show that two‐grid solution achieves the same accuracy as long as the mesh sizes satisfy H = O(h^1/2). Two numerical experiments are given to verify the effectiveness of the algorithm. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Nonconforming finite element methods with subgrid viscosity applied to advection‐diffusion‐reaction equations

A nonconforming (Crouzeix–Raviart) finite element method with subgrid viscosity is analyzed to approximate advection‐diffusion‐reaction equations. The error estimates are quasi‐optimal in the sense that keeping the Péclet number fixed, the estimates are suboptimal of order in the mesh size for the L²‐norm and optimal for the advective derivative on quasi‐uniform meshes. The method is also reformulated as a finite volume box scheme providing a reconstruction formula for the diffusive flux with local conservation properties. Numerical results are presented to illustrate the error analysis. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

On k‐detour subgraphs of hypercubes

A spanning subgraph G of a graph H is a k‐detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k‐detour subgraphs of the n‐dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k‐detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k‐detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008     

Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4 : Every 2‐edge‐connected graph G contains a spanning tree T with the property that for every vertex v. As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that . A corollary of this is that every k‐arc‐strong digraph D has an out‐branching B such that , where . We conjecture that in this case would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings , , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t, can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003     

On the existence of a rainbow 1‐factor in 1‐factorizations of K

Let be a 1‐factorization of the complete uniform hypergraph with and . We show that there exists a 1‐factor of whose edges belong to n different 1‐factors in . Such a 1‐factor is called a “rainbow” 1‐factor or an “orthogonal” 1‐factor. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 487–490, 2007     

Uniqueness of weak solutions in critical space of the 3‐D time‐dependent Ginzburg‐Landau equations for superconductivity

We prove the uniqueness of weak solutions of the 3‐D time‐dependent Ginzburg‐Landau equations for super‐conductivity with initial data (ψ₀, A₀)∈ L² under the hypothesis that (ψ, A) ∈ L^s(0, T; L^r,∞) × (0, T; with Coulomb gauge for any (r, s) and satisfying + = 1, + = 1, ≥ , ≥ and 3 < r ≤ 6, 3 < ≤ ∞. Here L^r,∞ ≡ is the Lorentz space. As an application, we prove a uniqueness result with periodic boundary condition when ψ₀ ∈ , A₀ ∈ L³ (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

On stable implicit difference scheme for hyperbolic–parabolic equations in a Hilbert space

The first‐order of accuracy difference scheme for approximately solving the multipoint nonlocal boundary value problem for the differential equation in a Hilbert space H, with self‐adjoint positive definite operator A is presented. The stability estimates for the solution of this difference scheme are established. In applications, the stability estimates for the solution of difference schemes of the mixed type boundary value problems for hyperbolic–parabolic equations are obtained. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Existence of 3‐chromatic Steiner quadruple systems

A Steiner quadruple system of order v (briefly SQS (v)) is a pair (X, ), where X is a v‐element set and is a set of 4‐element subsets of X (called blocks or quadruples), such that each 3‐element subset of X is contained in a unique block of . The chromatic number of an SQS(v)(X, ) is the smallest m for which there is a map such that for all , where . The system (X, ) is equitably m‐chromatic if there is a proper coloring with minimal m for which the numbers differ from each other by at most 1. Linek and Mendelsohn showed that an equitably 3‐chromatic SQS(v) exists for v ≡ 4, 8, 10 (mod 12), v ≥ 16. In this article we show that an equitably 3‐chromatic SQS(v) exists for v ≡ 2 (mod 12) with v > 2. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 469–477, 2007     

Arc‐chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree

A k‐digraph is a digraph in which every vertex has outdegree at most k. A ‐digraph is a digraph in which a vertex has either outdegree at most k or indegree at most l. Motivated by function theory, we study the maximum value Φ (k) (resp. ) of the arc‐chromatic number over the k‐digraphs (resp. ‐digraphs). El‐Sahili [3] showed that . After giving a simple proof of this result, we show some better bounds. We show and where θ is the function defined by . We then study in more detail properties of Φ and . Finally, we give the exact values of and for . © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 315–332, 2006     

Second‐order backward stochastic differential equations and fully nonlinear parabolic PDEs

For a d‐dimensional diffusion of the form dX_t = μ(X_t)dt + σ(X_t)dW_t and continuous functions f and g, we study the existence and uniqueness of adapted processes Y, Z, Γ, and A solving the second‐order backward stochastic differential equation (2BSDE) If the associated PDE has a sufficiently regular solution, then it follows directly from Itô's formula that the processes solve the 2BSDE, where ?? is the Dynkin operator of X without the drift term. The main result of the paper shows that if f is Lipschitz in Y as well as decreasing in Γ and the PDE satisfies a comparison principle as in the theory of viscosity solutions, then the existence of a solution (Y, Z,Γ, A) to the 2BSDE implies that the associated PDE has a unique continuous viscosity solution v and the process Y is of the form Y_t = v(t, X_t), t ∈ [0, T]. In particular, the 2BSDE has at most one solution. This provides a stochastic representation for solutions of fully nonlinear parabolic PDEs. As a consequence, the numerical treatment of such PDEs can now be approached by Monte Carlo methods. © 2006 Wiley Periodicals, Inc.     

Low‐curvature image simplifiers: Global regularity of smooth solutions and Laplacian limiting schemes

We consider a class of fourth‐order nonlinear diffusion equations motivated by Tumblin and Turk's “low‐curvature image simplifiers” for image denoising and segmentation. The PDE for the image intensity u is of the form where g(s) = k²/(k² + s²) is a “curvature” threshold and λ denotes a fidelity‐matching parameter. We derive a priori bounds for Δu that allow us to prove global regularity of smooth solutions in one space dimension, and a geometric constraint for finite‐time singularities from smooth initial data in two space dimensions. This is in sharp contrast to the second‐order Perona‐Malik equation (an ill‐posed problem), on which the original LCIS method is modeled. The estimates also allow us to design a finite difference scheme that satisfies discrete versions of the estimates, in particular, a priori bounds on the smoothness estimator in both one and two space dimensions. We present computational results that show the effectiveness of such algorithms. Our results are connected to recent results for fourth‐order lubrication‐type equations and the design of positivity‐preserving schemes for such equations. This connection also has relevance for other related fourth‐order imaging equations. © 2004 Wiley Periodicals, Inc.     

C‐perfect hypergraphs

Let ${\mathcal{H}}=({{X}},{\mathcal{E}})Let ${\mathcal{H}}=({{X}},{\mathcal{E}})$ be a hypergraph with vertex set X and edge set ${\mathcal{E}}$. A C‐coloring of ${\mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}\in{\mathcal{E}}$ (i.e. no edge is multicolored). We denote by $\bar{\chi}({\mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $\alpha({\mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}\in{\mathcal{E}}$, and $\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E \in {\mathcal{E}}$. The hypergraph ${\mathcal{H}}$ is called C‐perfect if $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$ holds for every induced subhypergraph ${\mathcal{H}}\prime\subseteq{\mathcal{H}}$. If ${\mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${\mathcal{H}}$ with $\tau({\mathcal{H}})\le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010     

Random mappings with exchangeable in‐degrees

In this article we introduce a new random mapping model, , which maps the set {1,2,…,n} into itself. The random mapping is constructed using a collection of exchangeable random variables which satisfy . In the random digraph, , which represents the mapping , the in‐degree sequence for the vertices is given by the variables , and, in some sense, can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components, and the size of a typical component can be expressed in terms of expectations of various functions of . We also consider two special examples of which correspond to random mappings with preferential and anti‐preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008