On the convergence of the midpoint method

The midpoint method is an iterative method for the solution of nonlinear equations in a Banach space. Convergence results for this method have been studied in [3, 4, 9, 12]. Here we show how to improve and extend these results. In particular, we use hypotheses on the second Fréchet derivative of the nonlinear operator instead of the third-derivative hypotheses employed in the previous results and we obtain Banach space versions of some results that were derived in [9, 12] only in the real or complex space. We also provide various examples that validate our results.      

Feynman’s Operational Calculi: Disentangling Away from the Origin

In this paper we develop a method of forming functions of noncommuting operators (or disentangling) using functions that are not necessarily analytic at the origin in ℂ ⁿ . The method of disentangling follows Feynman’s heuristic rules from in (Feynman in Phys. Rev. 84:18–128, 1951) a mathematically rigorous fashion, generalizing the work of Jefferies and Johnson and the present author in (Jefferies and Johnson in Russ. J. Math. 8:153–181, 2001) and (Jefferies et al. in J. Korean Math. Soc. 38:193–226, 2001). In fact, the work in (Jefferies and Johnson in Russ. J. Math. 8:153–181, 2001) and (Jefferies et al. in J. Korean Math. Soc. 38:193–226, 2001) allow only functions analytic in a polydisk centered at the origin in ℂ ⁿ while the method introduced in this paper enable functions that are not analytic at the origin to be used. It is shown that the disentangling formalism introduced here reduces to that of (Jefferies and Johnson in Russ. J. Math. 8:153–181, 2001) and (Jefferies et al. in J. Korean Math. Soc. 38:193–226, 2001) under the appropriate assumptions. A basic commutativity theorem is also established.     

A New Method for Finding the Characteristic Roots of E<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>/E<Subscript><Emphasis Type="Italic">m</Emphasis></Subscript>/1 Queues

In 1953, Smith (Proc Camb Philos Soc 49:449–461, 1953), and, following him, Syski (1960) suggested a method to find the waiting time distribution for one server queues with Erlang-n arrivals and Erlang-m service times by using characteristic roots. Syski shows that these roots can be determined from a very simple equation, but an equation of degree n + m. Syski also shows that almost all of the characteristic roots are complex. In this paper, we derive a set of equations, one for each complex root, which can be solved by Newton’s method using real arithmetic. This method simplifies the programming logic because it avoids deflation and the subsequent polishing of the roots. Using the waiting time distribution, Syski then derived the distribution of the number in the system after a departure. E _n /E _m /1 queues can also formulated as quasi birth-death (QBD) processes, and in this case, the characteristic roots discussed by Syski are closely related to the eigenvalues of the QBD process. The QBD process provides information about the number in system at random times, but they are much more difficult to formulate and solve.     

Further Results on the Robust Regulation of a One-Dimensional Dam-River System

In this paper, we consider a one-dimensional dam-river system studied by Chentouf and Wang (SIAM J. Control Optim. 47: 2275–2302, 2008). Then, using the frequency multiplier method, we provide a simple and alternative proof of stabilization and regulation results obtained in the work cited above. Moreover, we relax the conditions on the feedback gains involved in the feedback law and give a partial answer to the open problem left by the authors Chentouf and Wang (J. Optim. Theory Appl. 134: 223–239, 2007 and SIAM J. Control Optim. 47: 2275–2302, 2008) concerning the tuning of the gains.     

Uniqueness theorems of entire functions sharing a nonzero complex number with their difference operators

In this paper, we deal with a uniqueness question of entire functions sharing a nonzero complex number with their difference operators. The results in this paper improve Theorem 1.1 in Liu and Yang (Arch. Math. 92 (2009), 270–278) and deal with Question 1 in Liu and Yang (2009), where the entire functions are of finite orders.     

Extending the applicability of the Gauss–Newton method under average Lipschitz–type conditions

We extend the applicability of the Gauss–Newton method for solving singular systems of equations under the notions of average Lipschitz–type conditions introduced recently in Li et al. (J Complex 26(3):268–295, 2010). Using our idea of recurrent functions, we provide a tighter local as well as semilocal convergence analysis for the Gauss–Newton method than in Li et al. (J Complex 26(3):268–295, 2010) who recently extended and improved earlier results (Hu et al. J Comput Appl Math 219:110–122, 2008; Li et al. Comput Math Appl 47:1057–1067, 2004; Wang Math Comput 68(255):169–186, 1999). We also note that our results are obtained under weaker or the same hypotheses as in Li et al. (J Complex 26(3):268–295, 2010). Applications to some special cases of Kantorovich–type conditions are also provided in this study.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).     

On the Existence of Min-Max Minimal Torus

In this paper, we will study the existence problem of min-max minimal torus. We use classical conformal invariant geometric variational methods. We prove a theorem about the existence of min-max minimal torus in Theorem 5.1. First we prove a strong uniformization result (Proposition 3.1) using the method of Ahlfors and Bers (Ann. Math. 72(2):385–404, 1960). Then we use this proposition to choose good parameterization for our min-max sequences. We prove a compactification result (Lemma 4.1) similar to that of Colding and Minicozzi (Width and finite extinction time of Ricci flow, [math.DG], 2007), and then give bubbling convergence results similar to that of Ding et al. (Invent. math. 165:225–242, 2006). In fact, we get an approximating result similar to the classical deformation lemma (Theorem 1.1).     

An Explicit Formula for the Coefficients of the Saddle Point Method

Most standard textbooks about asymptotic approximations of integrals do not give explicit formulas for the coefficients of the asymptotic methods of Laplace and saddle point. In these techniques, those coefficients arise as the Taylor coefficients of a function defined in an implicit form, and the coefficients are not given by a closed algebraic formula. Despite this fact, we can extract from the literature some formulas of varying degrees of explicitness for those coefficients: Perron’s method (in Sitzungsber. Bayr. Akad. Wissensch. (Münch. Ber.), 191–219, 1917) offers an explicit computation in terms of the derivatives of an explicit function; in (de Bruijn, Asymptotic Methods in Analysis. Dover, New York, 1950) we can find a similar formula for the Laplace method which uses derivatives of an explicit function. Dingle (in Asymptotic Expansions: Their Derivation and Interpretation, Academic Press, New York, 1973) gives the coefficients of the saddle point method in terms of a contour integral. Perron’s method is rediscovered in (Campbell et al., Stud. Appl. Math. 77:151–172, 1987), but they also go farther and compute the above mentioned derivatives by means of a recurrence. The most recent contribution is (Wojdylo, SIAM Rev. 48(1):76–96, 2006), which rediscovers the Campbell, Fr?man and Walles’ formula and rewrites it in terms of Bell polynomials (in the Laplace method) using new ideas of combinatorial analysis which efficiently simplify and systematize the computations. In this paper we continue the research line of these authors. We combine the more systematic version of the saddle point method introduced in (López et al., J. Math. Anal. Appl. 354(1):347–359, 2009) with Wojdylo’s idea to derive a new and more explicit formula for the coefficients of the saddle point method, similar to Wojdylo’s formula for the coefficients of the Laplace method. As an example, we show the application of this formula to the Bessel function.     

Recurrence relations for semilocal convergence of a fifth-order method in Banach spaces

In this paper, we study the semilocal convergence for a fifth-order method for solving nonlinear equations in Banach spaces. The semilocal convergence of this method is established by using recurrence relations. We prove an existence-uniqueness theorem and give a priori error bounds which demonstrates the R-order of the method. As compared with the Jarratt method in Hernández and Salanova (Southwest J Pure Appl Math 1:29–40, 1999) and the Multi-super-Halley method in Wang et al. (Numer Algorithms 56:497–516, 2011), the differentiability conditions of the convergence of the method in this paper are mild and the R-order is improved. Finally, we give some numerical applications to demonstrate our approach.     

Two modified Dai-Yuan nonlinear conjugate gradient methods

In this paper, we propose two modified versions of the Dai-Yuan (DY) nonlinear conjugate gradient method. One is based on the MBFGS method (Li and Fukushima, J Comput Appl Math 129:15–35, 2001) and inherits all nice properties of the DY method. Moreover, this method converges globally for nonconvex functions even if the standard Armijo line search is used. The other is based on the ideas of Wei et al. (Appl Math Comput 183:1341–1350, 2006), Zhang et al. (Numer Math 104:561–572, 2006) and possesses good performance of the Hestenes-Stiefel method. Numerical results are also reported. This work was supported by the NSF foundation (10701018) of China.     

Multi-step nonlinear conjugate gradient methods for unconstrained minimization

Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput. Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent under certain assumptions. Numerical results are reported.     

Combinatorial Sublinear-Time Fourier Algorithms

We study the problem of estimating the best k term Fourier representation for a given frequency sparse signal (i.e., vector) A of length N≫k. More explicitly, we investigate how to deterministically identify k of the largest magnitude frequencies of [^(A)]\hat{\mathbf{A}} , and estimate their coefficients, in polynomial(k,log N) time. Randomized sublinear-time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem (Gilbert et al. in ACM STOC, pp. 152–161, 2002; Proceedings of SPIE Wavelets XI, 2005). In this paper we develop the first known deterministic sublinear-time sparse Fourier Transform algorithm which is guaranteed to produce accurate results. As an added bonus, a simple relaxation of our deterministic Fourier result leads to a new Monte Carlo Fourier algorithm with similar runtime/sampling bounds to the current best randomized Fourier method (Gilbert et al. in Proceedings of SPIE Wavelets XI, 2005). Finally, the Fourier algorithm we develop here implies a simpler optimized version of the deterministic compressed sensing method previously developed in (Iwen in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’08), 2008).     

A new hybrid algorithm for a system of equilibrium problems and variational inclusion

The purpose of this paper is to consider a shrinking projection method of finding the common element of the set of common fixed points for a finite family of a ξ-strict pseudo-contraction, the set of solutions of a systems of equilibrium problems and the set of solutions of variational inclusions. Then, we prove strong convergence theorems of the iterative sequence generated by the shrinking projection method under some suitable conditions in a real Hilbert space. Our results improve and extend recent results announced by Peng, Wang, Shyu and Yao (J Inequal Appl, 2008:15, Article ID 720371, 2008), Takahashi, Takeuchi and Kubota (J Math Anal Appl 341:276–286, 2008), Takahashi and Takahashi (Nonlinear Anal 69:1025–1033, 2008) and many others.     

A priori error estimates for space–time finite element discretization of semilinear parabolic optimal control problems

In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008; SIAM Control Optim 47(3):1301–1329, 2008) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and R?sch (SIAM J Control Optim 43:970–985, 2004), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls.     

Small Support Spline Riesz Wavelets in Low Dimensions

In Han and Shen (SIAM J. Math. Anal. 38:530–556, 2006), a family of univariate short support Riesz wavelets was constructed from uniform B-splines. A bivariate spline Riesz wavelet basis from the Loop scheme was derived in Han and Shen (J. Fourier Anal. Appl. 11:615–637, 2005). Motivated by these two papers, we develop in this article a general theory and a construction method to derive small support Riesz wavelets in low dimensions from refinable functions. In particular, we obtain small support spline Riesz wavelets from bivariate and trivariate box splines. Small support Riesz wavelets are desirable for developing efficient algorithms in various applications. For example, the short support Riesz wavelets from Han and Shen (SIAM J. Math. Anal. 38:530–556, 2006) were used in a surface fitting algorithm of Johnson et al. (J. Approx. Theory 159:197–223, 2009), and the Riesz wavelet basis from the Loop scheme was used in a very efficient geometric mesh compression algorithm in Khodakovsky et al. (Proceedings of SIGGRAPH, 2000).     

One-dimensional chemotaxis kinetic model

In this paper, we study a variation of the equations of a chemotaxis kinetic model and investigate it in one dimension. In fact, we use fractional diffusion for the chemoattractant in the Othmar–Dunbar–Alt system (Othmer in J Math Biol 26(3):263–298, 1988). This version was exhibited in Calvez in Amer Math Soc, pp 45–62, 2007 for the macroscopic well-known Keller–Segel model in all space dimensions. These two macroscopic and kinetic models are related as mentioned in Bournaveas, Ann Inst H Poincaré Anal Non Linéaire, 26(5):1871–1895, 2009, Chalub, Math Models Methods Appl Sci, 16(7 suppl):1173–1197, 2006, Chalub, Monatsh Math, 142(1–2):123–141, 2004, Chalub, Port Math (NS), 63(2):227–250, 2006. The model we study here behaves in a similar way to the original model in two dimensions with the spherical symmetry assumption on the initial data which is described in Bournaveas, Ann Inst H Poincaré Anal Non Linéaire, 26(5):1871–1895, 2009. We prove the existence and uniqueness of solutions for this model, as well as a convergence result for a family of numerical schemes. The advantage of this model is that numerical simulations can be easily done especially to track the blow-up phenomenon.     

Delannoy Orthants of Legendre Polytopes

We construct an n-dimensional polytope whose boundary complex is compressed and whose face numbers for any pulling triangulation are the coefficients of the powers of (x−1)/2 in the nth Legendre polynomial. We show that the non-central Delannoy numbers count all faces in the lexicographic pulling triangulation that contain a point in a given open generalized orthant. We thus provide a geometric interpretation of a relation between the central Delannoy numbers and Legendre polynomials, observed over 50 years ago (Good in Proc. Camb. Philos. Soc. 54:39–42, 1958; Lawden in Math. Gaz. 36:193–196, 1952; Moser and Zayachkowski in Scr. Math. 26:223–229, 1963). The polytopes we construct are closely related to the root polytopes introduced by Gelfand et al. (Arnold–Gelfand mathematical seminars: geometry and singularity theory, pp. 205–221. Birkhauser, Boston, 1996).     

Globally Convergent Three-Term Conjugate Gradient Methods that Use Secant Conditions and Generate Descent Search Directions for Unconstrained Optimization

In this paper, we propose a three-term conjugate gradient method based on secant conditions for unconstrained optimization problems. Specifically, we apply the idea of Dai and Liao (in Appl. Math. Optim. 43: 87–101, 2001) to the three-term conjugate gradient method proposed by Narushima et al. (in SIAM J. Optim. 21: 212–230, 2011). Moreover, we derive a special-purpose three-term conjugate gradient method for a problem, whose objective function has a special structure, and apply it to nonlinear least squares problems. We prove the global convergence properties of the proposed methods. Finally, some numerical results are given to show the performance of our methods.     

Topology of Hom complexes and test graphs for bounding chromatic number

The Hom complex of homomorphisms between two graphs was originally introduced to provide topological lower bounds on the chromatic number. In this paper we introduce new methods for understanding the topology of Hom complexes, mostly in the context of Γ-actions on graphs and posets (for some group Γ). We view the Hom(T, ⊙) and Hom(⊙, G) complexes as functors from graphs to posets, and introduce a functor (⊙)¹ from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations of the equivariant homotopy type of Hom complexes in terms of spaces of equivariant poset maps and Γ-twisted products of spaces. When P:= F(X) is the face poset of a simplicial complex X, this provides a useful way to control the topology of Hom complexes. These constructions generalize those of the second author from [17] as well as the calculation of the homotopy groups of Hom complexes from [8].