Multi-step hybrid methods for special second-order differential equations y″(t) = f(t,y(t))

In this paper, multi-step hybrid methods for solving special second-order differential equations y^″(t) = f(t,y(t)) are presented and studied. The new methods inherit the frameworks of RKN methods and linear multi-step methods and include two-step hybrid methods proposed by Coleman (IMA J. Numer. Anal. 23, 197–220, 8) as special cases. The order conditions of the methods were derived by using the SN-series defined on the set SNT of SN-trees. Based on the order conditions, we construct two explicit four-step hybrid methods, which are convergent of order six and seven, respectively. Numerical results show that our new methods are more efficient in comparison with the well-known high quality methods proposed in the scientific literature.     

Hybridization of accelerated gradient descent method

We present a gradient descent algorithm with a line search procedure for solving unconstrained optimization problems which is defined as a result of applying Picard-Mann hybrid iterative process on accelerated gradient descent S M method described in Stanimirovi? and Miladinovi? (Numer. Algor. 54, 503–520, 2010). Using merged features of both analyzed models, we show that new accelerated gradient descent model converges linearly and faster then the starting S M method which is confirmed trough displayed numerical test results. Three main properties are tested: number of iterations, CPU time and number of function evaluations. The efficiency of the proposed iteration is examined for the several values of the correction parameter introduced in Khan (2013).     

New error bounds for linear complementarity problems of Nekrasov matrices and <Emphasis Type="Italic">B</Emphasis>-Nekrasov matrices

New error bounds for the linear complementarity problems are given respectively when the involved matrices are Nekrasov matrices and B-Nekrasov matrices. Numerical examples are given to show that the new bounds are better respectively than those provided by García-Esnaola and Peña (Numer. Algor. 67(3), 655–667, 2014 and Numer. Algor. 72(2), 435–445, 2016) in some cases.     

Trigonometrical fitting conditions for two derivative Runge-Kutta methods

Two derivative Runge-Kutta methods are Runge-Kutta methods for problems of the form y^′ = f(y) that include the second derivative y^″ = g(y) = f^′(y)f(y) and were developed in the work of Chan and Tsai (Numer. Alg. 53, 171–194 2010). Explicit methods were considered and attention was given to the construction of methods that involve one evaluation of f and many evaluations of g per step. In this work, we consider trigonometrically fitted two derivative explicit Runge-Kutta methods of the general case that use several evaluations of f and g per step; trigonometrically fitting conditions for this general case are given. Attention is given to the construction of methods that involve several evaluations of f and one evaluation of g per step. We modify methods with stages up to four, with three f and one g evaluation and with four f and one g, evaluation based on the fourth and fifth order methods presented in Chan and Tsai (Numer. Alg. 53, 171–194 2010). We provide numerical results to demonstrate the efficiency of the new methods using four test problems.     

<Emphasis Type="Italic">l</Emphasis><Subscript>1</Subscript>-<Emphasis Type="Italic">l</Emphasis><Subscript>2</Subscript> regularization of split feasibility problems

Numerous problems in signal processing and imaging, statistical learning and data mining, or computer vision can be formulated as optimization problems which consist in minimizing a sum of convex functions, not necessarily differentiable, possibly composed with linear operators and that in turn can be transformed to split feasibility problems (SFP); see for example Censor and Elfving (Numer. Algorithms 8, 221–239 1994). Each function is typically either a data fidelity term or a regularization term enforcing some properties on the solution; see for example Chaux et al. (SIAM J. Imag. Sci. 2, 730–762 2009) and references therein. In this paper, we are interested in split feasibility problems which can be seen as a general form of Q-Lasso introduced in Alghamdi et al. (2013) that extended the well-known Lasso of Tibshirani (J. R. Stat. Soc. Ser. B 58, 267–288 1996). Q is a closed convex subset of a Euclidean m-space, for some integer m ≥ 1, that can be interpreted as the set of errors within given tolerance level when linear measurements are taken to recover a signal/image via the Lasso. Inspired by recent works by Lou and Yan (2016), Xu (IEEE Trans. Neural Netw. Learn. Syst. 23, 1013–1027 2012), we are interested in a nonconvex regularization of SFP and propose three split algorithms for solving this general case. The first one is based on the DC (difference of convex) algorithm (DCA) introduced by Pham Dinh Tao, the second one is nothing else than the celebrate forward-backward algorithm, and the third one uses a method introduced by Mine and Fukushima. It is worth mentioning that the SFP model a number of applied problems arising from signal/image processing and specially optimization problems for intensity-modulated radiation therapy (IMRT) treatment planning; see for example Censor et al. (Phys. Med. Biol. 51, 2353–2365, 2006).     

On modified Gordon-Wixom interpolation schemes and their applications to nonlinear and exterior domain problems

We introduce and study extensions and modifications of the Gordon-Wixom transfinite barycentric interpolation scheme (Gordon and Wixom, SIAM J. Numer. Anal. 11(5), 909–933, 1974). We demonstrate that the modified Gordon-Wixom scheme proposed in Belyaev and Fayolle (Comput. Graph. 51, 74–80, 2015) reproduces harmonic quadratic polynomials in convex domains. We adapt the scheme for dealing with the exterior of a bounded domain and for the exterior of a disk, where we demonstrate that our interpolation formula reproduces harmonic functions. Finally, we show how to adapt the Gordon-Wixom approach for approximating p-harmonic functions and to derive computationally efficient approximations of the solutions to boundary value problems involving the p-Laplacian.     

Generalized sinc-Gaussian sampling involving derivatives

The generalized sampling expansion which uses samples from a bandlimited function f and its first r derivatives was first introduced by Linden and Abramson (Inform. Contr. 3, 26–31, 1960) and it was extended in different situations by some authors through the last fifty years. The use of the generalized sampling series in approximation theory is limited because of the slow convergence. In this paper, we derive a modification of a generalized sampling involving derivatives, which is studied by Shin (Commun. Korean Math. Soc. 17, 731–740, 2002), using a Gaussian multiplier. This modification is introduced for wider classes, the class of entire functions including unbounded functions on ? and the class of analytic functions in a strip. It highly improves the convergence rate of the generalized sampling which will be of exponential order. We will show that many known results included in Sampl. Theory Signal Image Process. 9, 199–221 (2007) and Numer. Funct. Anal. Optim. 36, 419–437 (2015) are special cases of our results. Numerical examples show a rightly good agreement with our theoretical analysis.     

Poset Entropy Versus Number of Linear Extensions: The Width-2 Case

Kahn and Kim (J. Comput. Sci. 51, 3, 390–399, 1995) have shown that for a finite poset P, the entropy of the incomparability graph of P (normalized by multiplying by the order of P) and the base-2 logarithm of the number of linear extensions of P are within constant factors from each other. The tight constant for the upper bound was recently shown to be 2 by Cardinal et al. (Combinatorica 33, 655–697, 2013). Here, we refine this last result in case P has width 2: we show that the constant can be replaced by 2?ε if one also takes into account the number of connected components of size 2 in the incomparability graph of P. Our result leads to a better upper bound for the number of comparisons in algorithms for the problem of sorting under partial information.     

An hp finite element method for 4th order singularly perturbed problems

We present the analysis for the hp finite element approximation of the solution to singularly perturbed fourth order problems, using a balanced norm. In Panaseti et al. (2016) it was shown that the hp version of the Finite Element Method (FEM) on the so-called Spectral Boundary Layer Mesh yields robust exponential convergence when the error is measured in the natural energy norm associated with the problem. In the present article we sharpen the result by showing that the same hp-FEM on the Spectral Boundary Layer Mesh gives robust exponential convergence in a stronger, more balanced norm. As a corollary we also get robust exponential convergence in the maximum norm. The analysis is based on the ideas in Roos and Franz (Calcolo 51, 423–440, 2014) and Roos and Schopf (ZAMM 95, 551–565, 2015) and the recent results in Melenk and Xenophontos (2016). Numerical examples illustrating the theory are also presented.     

Directed Partial Orders on Complex Numbers and Quaternions over Non-Archimedean Linearly Ordered Fields

Let F be a non-archimedean linearly ordered field, and C and H be the field of complex numbers and the division algebra of quaternions over F, respectively. In this paper, a class of directed partial orders on C are constructed directly and concretely using additive subgroup of F ⁺. This class of directed partial orders includes those given in Rump and Wang (J. Algebra 400, 1–7, 2014), and Yang (J. Algebra 295(2), 452–457, 2006) as special cases and we conjecture that it covers all directed partial orders on C such that 1 > 0. It turns out that this construction also works very well on H. We note that none of these directed partial orders is a lattice order on C or H.     

Globally convergent Jacobi methods for positive definite matrix pairs

The paper derives and investigates the Jacobi methods for the generalized eigenvalue problem A x = λ B x, where A is a symmetric and B is a symmetric positive definite matrix. The methods first “normalize” B to have the unit diagonal and then maintain that property during the iterative process. The global convergence is proved for all such methods. That result is obtained for the large class of generalized serial strategies from Hari and Begovi? Kova? (Trans. Numer. Anal. (ETNA) 47, 107–147, 2017). Preliminary numerical tests confirm a high relative accuracy of some of those methods, provided that both matrices are positive definite and the spectral condition numbers of Δ _A AΔ _A and Δ _B BΔ _B are small, for some nonsingular diagonal matrices Δ _A and Δ _B .     

Some <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Rigidity Results for Complete Manifolds with Harmonic Curvature

Let (M ⁿ , g)(n ≥ 3) be an n-dimensional complete Riemannian manifold with harmonic curvature and positive Yamabe constant. Denote by R and R m? the scalar curvature and the trace-free Riemannian curvature tensor of M, respectively. The main result of this paper states that R m? goes to zero uniformly at infinity if for \(p\geq \frac n2\), the L ^p -norm of R m? is finite. Moreover, If R is positive, then (M ⁿ , g) is compact. As applications, we prove that (M ⁿ , g) is isometric to a spherical space form if for \(p\geq \frac n2\), R is positive and the L ^p -norm of R m? is pinched in [0, C ₁), where C ₁ is an explicit positive constant depending only on n, p, R and the Yamabe constant. We give an isolation theorem of the trace-free Ricci curvature tensor of compact locally conformally flat Riemannian n-manifolds with constant positive scalar curvature, which extends Theorem 1 of Hebey and M. Vaugon (J. Geom. Anal. 6, 531–553, 1996). This result is sharp, and we can precisely characterize the case of equality. In particular, when n = 4, we recover results by Gursky (Indiana Univ. Math. J. 43, 747–774, 1994; Ann. Math. 148, 315–337, 1998).     

Some matrix functional equations

We investigate the pair of matrix functional equations G(x)F(y) = G(xy) and G(x)G(y) = F(y/x), featuring the two independent scalar variables x and y and the two N×N matrices F(z) andG(z) (with N an arbitrary positive integer and the elements of these two matrices functions of the scalar variable z). We focus on the simplest class of solutions, i.e., on matrices all of whose elements are analytic functions of the independent variable. While in the scalar (N = 1) case this pair of functional equations only possess altogether trivial constant solutions, in the matrix (N > 1) case there are nontrivial solutions. These solutions satisfy the additional pair of functional equations F(x)G(y) = G(y/x) andF(x)F(y) = F(xy), and an endless hierarchy of other functional equations featuring more than two independent variables.     

The Relaxed Edge-Coloring Game and <Emphasis Type="Italic">k</Emphasis>-Degenerate Graphs

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ?j and d≥2j+2 for 0≤j≤Δ?1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k?1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k?j and d≥h(k,j).     

Contractive Hilbert modules and their dilations

In this note, we show that a quasi-free Hilbert module R defined over the polydisk algebra with kernel function k(z,w) admits a unique minimal dilation (actually an isometric co-extension) to the Hardy module over the polydisk if and only if S ^?1(z, w)k(z, w) is a positive kernel function, where S(z,w) is the Szegö kernel for the polydisk. Moreover, we establish the equivalence of such a factorization of the kernel function and a positivity condition, defined using the hereditary functional calculus, which was introduced earlier by Athavale [8] and Ambrozie, Englis and Müller [2]. An explicit realization of the dilation space is given along with the isometric embedding of the module R in it. The proof works for a wider class of Hilbert modules in which the Hardy module is replaced by more general quasi-free Hilbert modules such as the classical spaces on the polydisk or the unit ball in ? ^m . Some consequences of this more general result are then explored in the case of several natural function algebras.     

On Measure Contraction Property without Ricci Curvature Lower Bound

Measure contraction properties M C P (K, N) are synthetic Ricci curvature lower bounds for metric measure spaces which do not necessarily have smooth structures. It is known that if a Riemannian manifold has dimension N, then M C P (K, N) is equivalent to Ricci curvature bounded below by K. On the other hand, it was observed in Rifford (Math. Control Relat. Fields 3(4), 467–487 2013) that there is a family of left invariant metrics on the three dimensional Heisenberg group for which the Ricci curvature is not bounded below. Though this family of metric spaces equipped with the Harr measure satisfy M C P (0,5). In this paper, we give sufficient conditions for a 2n+1 dimensional weakly Sasakian manifold to satisfy M C P (0, 2n + 3). This extends the above mentioned result on the Heisenberg group in Rifford (Math. Control Relat. Fields 3(4), 467–487 2013).     

A new unicity theorem and Erdös’ problem for polarized semi-abelian varieties

In 1988 Erdös asked if the prime divisors of x ⁿ ? 1 for all n = 1, 2, … determine the given integer x; the problem was affirmatively answered by Corrales-Rodrigáñez and Schoof (J Number Theory 64:276–290, 1997) [but a solution could also be deduced from an earlier result of Schinzel (Bull Acad Polon Sci 8:307–309, 2007)] together with its elliptic version. Analogously, Yamanoi (Forum Math 16:749–788, 2004) proved that the support of the pulled-back divisor f ^* D of an ample divisor on an abelian variety A by an algebraically non-degenerate entire holomorphic curve f : C → A essentially determines the pair (A, D). By making use of the main theorem of Noguchi (Forum Math 20:469–503, 2008) we here deal with this problem for semi-abelian varieties; namely, given two polarized semi-abelian varieties (A ₁, D ₁), (A ₂, D ₂) and algebraically non-degenerate entire holomorphic curves f _i : C → A _i , i = 1, 2, we classify the cases when the inclusion \({{\rm{Supp}}\, f_1^*D_1\subset {\rm{Supp}}\, f_2^* D_2}\) holds. We shall remark in §5 that these methods yield an affirmative answer to a question of Lang formulated in 1966. Our answer is more general and more geometric than the original question. Finally, we interpret the main result of Corvaja and Zannier (Invent Math 149:431–451, 2002) to provide an arithmetic counterpart in the toric case.     

Numerical solution and structural analysis of two-dimensional integral-algebraic equations

The υ-smoothing property of a one-dimensional Volterra integral operator and some projectors (Liang and Brumer, SIAM J. Numer. Anal. 51, 2238–2259 (2013)) are extended for two-dimensional integral-algebraic equations (TIAEs). Using these concepts, we decompose the given general TIAEs into mixed systems of two-dimensional Volterra integral equations (TVIEs) consisting of second- and first-kind TVIEs. Numerical technique based on the Chebyshev polynomial collocation methods is presented for the solution of the mixed TVIE system. Global convergence results are established and the performance of the numerical scheme is illustrated by means of some test problems.     

Zooming from global to local: a multiscale RBF approach

Because physical phenomena on Earth’s surface occur on many different length scales, it makes sense when seeking an efficient approximation to start with a crude global approximation, and then make a sequence of corrections on finer and finer scales. It also makes sense eventually to seek fine scale features locally, rather than globally. In the present work, we start with a global multiscale radial basis function (RBF) approximation, based on a sequence of point sets with decreasing mesh norm, and a sequence of (spherical) radial basis functions with proportionally decreasing scale centered at the points. We then prove that we can “zoom in” on a region of particular interest, by carrying out further stages of multiscale refinement on a local region. The proof combines multiscale techniques for the sphere from Le Gia, Sloan and Wendland, SIAM J. Numer. Anal. 48 (2010) and Applied Comp. Harm. Anal. 32 (2012), with those for a bounded region in ? ^d from Wendland, Numer. Math. 116 (2010). The zooming in process can be continued indefinitely, since the condition numbers of matrices at the different scales remain bounded. A numerical example illustrates the process.     

Detailed error analysis for a fractional Adams method with graded meshes

We consider a fractional Adams method for solving the nonlinear fractional differential equation \(\,^{C}_{0}D^{\alpha }_{t} y(t) = f(t, y(t)), \, \alpha >0\), equipped with the initial conditions \(y^{(k)} (0) = y_{0}^{(k)}, k=0, 1, \dots , \lceil \alpha \rceil -1\). Here, α may be an arbitrary positive number and ?α? denotes the smallest integer no less than α and the differential operator is the Caputo derivative. Under the assumption \(\,^{C}_{0}D^{\alpha }_{t} y \in C^{2}[0, T]\), Diethelm et al. (Numer. Algor. 36, 31–52, 2004) introduced a fractional Adams method with the uniform meshes t _n = T(n/N),n = 0,1,2,…,N and proved that this method has the optimal convergence order uniformly in t _n , that is O(N ^?2) if α > 1 and O(N ^?1?α ) if α ≤ 1. They also showed that if \(\,^{C}_{0}D^{\alpha }_{t} y(t) \notin C^{2}[0, T]\), the optimal convergence order of this method cannot be obtained with the uniform meshes. However, it is well-known that for y ∈ C ^m [0,T] for some \(m \in \mathbb {N}\) and 0 < α < m, the Caputo fractional derivative \(\,^{C}_{0}D^{\alpha }_{t} y(t) \) takes the form “\(\,^{C}_{0}D^{\alpha }_{t} y(t) = c t^{\lceil \alpha \rceil -\alpha } + \text {smoother terms}\)” (Diethelm et al. Numer. Algor. 36, 31–52, 2004), which implies that \(\,^{C}_{0}D^{\alpha }_{t} y \) behaves as t ^?α??α which is not in C ²[0,T]. By using the graded meshes t _n = T(n/N) ^r ,n = 0,1,2,…,N with some suitable r > 1, we show that the optimal convergence order of this method can be recovered uniformly in t _n even if \(\,^{C}_{0}D^{\alpha }_{t} y\) behaves as t ^σ ,0 < σ < 1. Numerical examples are given to show that the numerical results are consistent with the theoretical results.