Approximation of integrable functions based on \phi -transform

Let \(E\) be a bounded subset of real line which contains its infimum and supremum. In this paper, we have defined the \(\phi -\) transform and its inverse, where \(\phi \) is a function from \(E\) into \((0,1]\) . We will have shown that real-valued integrable functions on \([a, b]\) and real-valued continuous functions on \(E\) can be approximated by this transformation with an arbitrary precision.     

Łukasiewicz logic and Riesz spaces

We initiate a deep study of Riesz MV-algebras which are MV-algebras endowed with a scalar multiplication with scalars from \([0,1]\) . Extending Mundici’s equivalence between MV-algebras and \(\ell \) -groups, we prove that Riesz MV-algebras are categorically equivalent to unit intervals in Riesz spaces with strong unit. Moreover, the subclass of norm-complete Riesz MV-algebras is equivalent to the class of commutative unital C \(^*\) -algebras. The propositional calculus \({\mathbb R}{\mathcal L}\) that has Riesz MV-algebras as models is a conservative extension of ?ukasiewicz \(\infty \) -valued propositional calculus and is complete with respect to evaluations in the standard model \([0,1]\) . We prove a normal form theorem for this logic, extending McNaughton theorem for ? ukasiewicz logic. We define the notions of quasi-linear combination and quasi-linear span for formulas in \({\mathbb R}{\mathcal L},\) and relate them with the analogue of de Finetti’s coherence criterion for \({\mathbb R}{\mathcal L}\) .     

A note on tensor chain approximation

This paper deals with the approximation of \(d\) -dimensional tensors, as discrete representations of arbitrary functions \(f(x_1,\ldots ,x_d)\) on \([0,1]^d\) , in the so-called tensor chain format. The main goal of this paper is to show that the construction of a tensor chain approximation is possible using skeleton/cross approximation type methods. The complete algorithm is described, computational issues are discussed in detail and the complexity of the algorithm is shown to be linear in \(d\) . Some numerical examples are given to validate the theoretical results.     

Richardson Extrapolation on Some Recent Numerical Quadrature Formulas for Singular and Hypersingular Integrals and Its Study of Stability

Recently, we derived some new numerical quadrature formulas of trapezoidal rule type for the integrals \(I^{(1)}[g]=\int ^b_a \frac{g(x)}{x-t}\,dx\) and \(I^{(2)}[g]=\int ^b_a \frac{g(x)}{(x-t)^2}\,dx\) . These integrals are not defined in the regular sense; \(I^{(1)}[g]\) is defined in the sense of Cauchy Principal Value while \(I^{(2)}[g]\) is defined in the sense of Hadamard Finite Part. With \(h=(b-a)/n, \,n=1,2,\ldots \) , and \(t=a+kh\) for some \(k\in \{1,\ldots ,n-1\}, \,t\) being fixed, the numerical quadrature formulas \({Q}^{(1)}_n[g]\) for \(I^{(1)}[g]\) and \(Q^{(2)}_n[g]\) for \(I^{(2)}[g]\) are $$\begin{aligned} {Q}^{(1)}_n[g]=h\sum ^n_{j=1}f(a+jh-h/2),\quad f(x)=\frac{g(x)}{x-t}, \end{aligned}$$ and $$\begin{aligned} Q^{(2)}_n[g]=h\sum ^n_{j=1}f(a+jh-h/2)-\pi ^2g(t)h^{-1},\quad f(x)=\frac{g(x)}{(x-t)^2}. \end{aligned}$$ We provided a complete analysis of the errors in these formulas under the assumption that \(g\in C^\infty [a,b]\) . We actually show that $$\begin{aligned} I^{(k)}[g]-{Q}^{(k)}_n[g]\sim \sum ^\infty _{i=1} c^{(k)}_ih^{2i}\quad \text {as}\,n \rightarrow \infty , \end{aligned}$$ the constants \(c^{(k)}_i\) being independent of \(h\) . In this work, we apply the Richardson extrapolation to \({Q}^{(k)}_n[g]\) to obtain approximations of very high accuracy to \(I^{(k)}[g]\) . We also give a thorough analysis of convergence and numerical stability (in finite-precision arithmetic) for them. In our study of stability, we show that errors committed when computing the function \(g(x)\) , which form the main source of errors in the rest of the computation, propagate in a relatively mild fashion into the extrapolation table, and we quantify their rate of propagation. We confirm our conclusions via numerical examples.     

Solving Convection-Diffusion Problems on Curved Domains by Extensions from Subdomains

We present a technique for numerically solving convection-diffusion problems in domains $\varOmega $ with curved boundary. The technique consists in approximating the domain $\varOmega $ by polyhedral subdomains $\mathsf{{D}}_h$ where a finite element method is used to solve for the approximate solution. The approximation is then suitably extended to the remaining part of the domain $\varOmega $ . This approach allows for the use of only polyhedral elements; there is no need of fitting the boundary in order to obtain an accurate approximation of the solution. To achieve this, the boundary condition on the border of $\varOmega $ is transferred to the border of $\mathsf{D }_h$ by using simple line integrals. We apply this technique to the hybridizable discontinuous Galerkin method and provide extensive numerical experiments showing that, whenever the distance of $\mathsf{{D}}_h$ to $\partial \varOmega $ is of order of the meshsize $h$ , the convergence properties of the resulting method are the same as those for the case in which $\varOmega =\mathsf{{D}}_h$ . We also show numerical evidence indicating that the ratio of the $L^2(\varOmega )$ norm of the error in the scalar variable computed with $d>0$ to that of that computed with $d=0$ remains constant (and fairly close to one), whenever the distance $d$ is proportional to $\min \{h,Pe^{-1}\}/(k+1)^2$ , where $Pe$ is the so-called Péclet number.     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

Strong Conflict-Free Coloring for Intervals

We consider the \(k\) -strong conflict-free ( \(k\) -SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\) . We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\) . In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\) . We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\) , a quasipolynomial time algorithm to decide the existence of a \(k\) -SCF coloring that uses at most \(q\) colors.     

Two-Grid Methods for Hermitian positive definite linear systems connected with an order relation

Given a multigrid procedure for linear systems with coefficient matrices $A_n,$ we discuss the optimality of a related multigrid procedure with the same smoother and the same projector, when applied to properly related algebraic problems with coefficient matrices $B_n$ : we assume that both $A_n$ and $B_n$ are Hermitian positive definite with $A_n\le \vartheta B_n,$ for some positive $\vartheta $ independent of $n.$ In this context we prove the Two-Grid Method optimality. We apply this elementary strategy for designing a multigrid solution for modifications of multilevel structured linear systems, in which the Hermitian positive definite coefficient matrix is banded in a multilevel sense. As structured matrices, Toeplitz, circulants, Hartley, sine ( $\tau $ class) and cosine algebras are considered. In such a way, several linear systems arising from the approximation of integro–differential equations with various boundary conditions can be efficiently solved in linear time (with respect to the size of the algebraic problem). Some numerical experiments are presented and discussed, both with respect to Two-Grid and multigrid procedures.     

The Nonconvergence of h-Refinement in Prolate Elements

Prolate elements are a “plug-compatible” modification of spectral elements in which Legendre polynomials are replaced by prolate spheroidal wave functions of order zero. Prolate functions contain a“bandwidth parameter” $c \ge 0 $ c ≥ 0 whose value is crucial to numerical performance; the prolate functions reduce to Legendre polynomials for $c\,=\,0$ c = 0 . We show that the optimal bandwidth parameter $c$ c not only depends on the number of prolate modes per element $N$ N , but also on the element widths $h$ h . We prove that prolate elements lack $h$ h -convergence for fixed $c$ c in the sense that the error does not go to zero as the element size $h$ h is made smaller and smaller. Furthermore, the theoretical predictions that Chebyshev and Legendre polynomials require $\pi $ π degrees of freedom per wavelength to resolve sinusoidal functions while prolate series need only 2 degrees of freedom per wavelength are asymptotic limits as $N \rightarrow \infty $ N → ∞ ; we investigate the rather different behavior when $N \sim O(4-10)$ N ～ O ( 4 ? 10 ) as appropriate for spectral elements and prolate elements. On the other hand, our investigations show that there are certain combinations of $N,\,h$ N , h and $c>0$ c > 0 where a prolate basis clearly outperforms the Legendre polynomial approximation.     

The Minimum Vulnerability Problem

We revisit the problem of finding \(k\) paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the \(k\) paths. We provide a \({\lfloor {k/2}\rfloor }\) -approximation algorithm for this problem, improving the best previous approximation factor of \(k-1\) . We also provide the first approximation algorithm for the problem with a sublinear approximation factor of \(O(n^{3/4})\) , where \(n\) is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to \(O(\sqrt{n})\) . While the problem is NP-hard, and even hard to approximate to within an \(O(\log n)\) factor, we show that the problem is polynomially solvable when \(k\) is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of \(k\) . We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter \(r\) that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.     

The categories L-\mathbf{Top}_{0} and L-\mathbf{Sob} as epireflective hulls

We show that the category \(L\) - \(\mathbf{Top}_{0}\) of \(T_{0}\) - \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}\) of \(L\) -topological spaces and the category \(L\) - \(\mathbf{Sob}\) of sober \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}_{0}\) .     

A P_N P_M{-} CPR Framework for Hyperbolic Conservation Laws

The correction procedure via reconstruction (CPR) method is a discontinuous nodal formulation unifying several well-known methods in a simple finite difference like manner. The \(P_NP_M{-} CPR \) formulation is an extension of \(P_NP_M\) or the reconstructed discontinuous Galerkin (RDG) method to the CPR framework. It is a hybrid finite volume and discontinuous Galerkin (DG) method, in which neighboring cells are used to build a higher order polynomial than the solution representation in the cell under consideration. In this paper, we present several \(P_NP_M\) schemes under the CPR framework. Many interesting schemes with various orders of accuracy and efficiency are developed. The dispersion and dissipation properties of those methods are investigated through a Fourier analysis, which shows that the \(P_NP_M{-} CPR \) method is dependent on the position of the solution points. Optimal solution points for 1D \(P_NP_M{-} CPR \) schemes which can produce expected order of accuracy are identified. In addition, the \(P_NP_M{-} CPR \) method is extended to solve 2D inviscid flow governed by the Euler equations and several numerical tests are performed to assess its performance.     

Local Discontinuous Galerkin Methods for One-Dimensional Second Order Fully Nonlinear Elliptic and Parabolic Equations

This paper is concerned with developing accurate and efficient nonstandard discontinuous Galerkin methods for fully nonlinear second order elliptic and parabolic partial differential equations (PDEs) in the case of one spatial dimension. The primary goal of the paper to develop a general framework for constructing high order local discontinuous Galerkin (LDG) methods for approximating viscosity solutions of these fully nonlinear PDEs which are merely continuous functions by definition. In order to capture discontinuities of the first order derivative $u_x$ of the solution $u$ , two independent functions $q^-$ and $q^+$ are introduced to approximate one-sided derivatives of $u$ . Similarly, to capture the discontinuities of the second order derivative $u_{xx}$ , four independent functions $p^{- -}, p^{- +}, p^{+ -}$ , and $p^{+ +}$ are used to approximate one-sided derivatives of $q^-$ and $q^+$ . The proposed LDG framework, which is based on a nonstandard mixed formulation of the underlying PDE, embeds a given fully nonlinear problem into a mostly linear system of equations where the given nonlinear differential operator must be replaced by a numerical operator which allows multiple value inputs of the first and second order derivatives $u_x$ and $u_{xx}$ . An easy to verify set of criteria for constructing “good” numerical operators is also proposed. It consists of consistency and generalized monotonicity. To ensure such a generalized monotonicity property, the crux of the construction is to introduce the numerical moment in the numerical operator, which plays a critical role in the proposed LDG framework. The generalized monotonicity gives the LDG methods the ability to select the viscosity solution among all possible solutions. The proposed framework extends a companion finite difference framework developed by Feng and Lewis (J Comp Appl Math 254:81–98, 2013) and allows for the approximation of fully nonlinear PDEs using high order polynomials and non-uniform meshes. Numerical experiments are also presented to demonstrate the accuracy, efficiency and utility of the proposed LDG methods.     

Gaussian,Lobatto and Radau positive quadrature rules with a prescribed abscissa

For a given $\theta \in (a,b)$ , we investigate the question whether there exists a positive quadrature formula with maximal degree of precision which has the prescribed abscissa $\theta $ plus possibly $a$ and/or $b$ , the endpoints of the interval of integration. This study relies on recent results on the location of roots of quasi-orthogonal polynomials. The above positive quadrature formulae are useful in studying problems in one-sided polynomial $L_1$ approximation.     

Single-processor scheduling with time restrictions

We consider the following list scheduling problem. We are given a set \(S\) of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in \(S\) , the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer \(B \ge 2\) , no unit time interval \([x, x+1)\) is allowed to intersect more than \(B\) jobs for any real \(x\) . It is not surprising that this problem is NP-hard when the value \(B\) is variable (which is typical of many scheduling problems). There are several real world situations for which this restriction is natural. For example, suppose in addition to our jobs being executed sequentially on a single main processor, each job also requires the use of one of \(B\) identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time in order to reset itself. In this way, it is never possible for more than \(B\) jobs to be worked on during any unit interval. In this paper we carry out a classical worst-case analysis for this situation. In particular, we show that any permutation of the jobs can be processed within a factor of \(2-1/(B-1)\) of the optimum (plus an additional small constant) when \(B \ge 3\) and this factor is best possible. For the case \(B=2\) , the situation is rather different, and in this case the corresponding factor we establish is \(4/3\) (plus an additional small constant), which is also best possible. It is fairly rare that best possible bounds can be obtained for the competitive ratios of list scheduling problems of this general type.     

Optimal quadrature formulas in the sense of Sard in W_2^{(m,m-1)} space

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the $W_2^{(m,m-1)}(0,1)$ space. Using the Sobolev’s method we obtain new optimal quadrature formulas of such type for $N+1\ge m$ , where $N+1$ is the number of the nodes. Moreover, explicit formulas of the optimal coefficients are obtained. We investigate the order of convergence of the optimal formula for $m=1$ and prove an asymptotic optimality of such a formula in the Sobolev space $L_2^{(1)}(0,1)$ . It turns out that the error of the optimal quadrature formula in $W_2^{(1,0)}(0,1)$ is less than the error of the optimal quadrature formula given in the $L_2^{(1)}(0,1)$ space. The obtained optimal quadrature formula in the $W_2^{(m,m-1)}(0,1)$ space is exact for $\exp (-x)$ and $P_{m-2}(x)$ , where $P_{m-2}(x)$ is a polynomial of degree $m-2$ . Furthermore, some numerical results, which confirm the obtained theoretical results of this work, are given.     

Some kinds of primitive and non-primitive words

If the length of a primitive word \(p\) is equal to the length of another primitive word \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . This was obtained separately by Tetsuo Moriya in 2008 and Shyr and Yu in 1994. In this paper, we prove that if the length of \(p\) is divisible by the length of \(q\) and the length of \(p\) is less than or equal to \(m\) times the length of \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . Then we show that if \(uv,u\) are non-primitive words and the length of \(u\) is divisible by the length \(v\) or one of the length of \(u\) and \(uv\) is odd for any two nonempty words \(u\) and \(v\) , then \(u\) is a power of \(v\) .     

Shape preservation of scientific data through rational fractal splines

Fractal interpolation is a modern technique in approximation theory to fit and analyze scientific data. We develop a new class of $\mathcal C ^1$ - rational cubic fractal interpolation functions, where the associated iterated function system uses rational functions of the form $\frac{p_i(x)}{q_i(x)},$ where $p_i(x)$ and $q_i(x)$ are cubic polynomials involving two shape parameters. The rational cubic iterated function system scheme provides an additional freedom over the classical rational cubic interpolants due to the presence of the scaling factors and shape parameters. The classical rational cubic functions are obtained as a special case of the developed fractal interpolants. An upper bound of the uniform error of the rational cubic fractal interpolation function with an original function in $\mathcal C ^2$ is deduced for the convergence results. The rational fractal scheme is computationally economical, very much local, moderately local or global depending on the scaling factors and shape parameters. Appropriate restrictions on the scaling factors and shape parameters give sufficient conditions for a shape preserving rational cubic fractal interpolation function so that it is monotonic, positive, and convex if the data set is monotonic, positive, and convex, respectively. A visual illustration of the shape preserving fractal curves is provided to support our theoretical results.     

Interpolation splines minimizing a semi-norm

Using S.L. Sobolev’s method, we construct the interpolation splines minimizing the semi-norm in $K_2(P_2)$ , where $K_2(P_2)$ is the space of functions $\phi $ such that $\phi ^{\prime } $ is absolutely continuous, $\phi ^{\prime \prime } $ belongs to $L_2(0,1)$ and $\int _0^1(\varphi ^{\prime \prime }(x)+\varphi (x))^2dx<\infty $ . Explicit formulas for coefficients of the interpolation splines are obtained. The resulting interpolation spline is exact for the trigonometric functions $\sin x$ and $\cos x$ . Finally, in a few numerical examples the qualities of the defined splines and $D^2$ -splines are compared. Furthermore, the relationship of the defined splines with an optimal quadrature formula is shown.     

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

The Induced Graph Matching problem asks to find \(k\) disjoint induced subgraphs isomorphic to a given graph  \(H\) in a given graph \(G\) such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in \(k\) on claw-free graphs when \(H\) is a fixed connected graph, and even admits a polynomial kernel when  \(H\) is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove \(\mathsf {W}[1]\) -hardness of Induced Graph Matching on graphs excluding \(K_{1,4}\) as an induced subgraph, for any fixed complete graph \(H\) . In particular, we show that Independent Set is \(\mathsf {W}[1]\) -hard on \(K_{1,4}\) -free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or \(\mathsf {NP}\) -complete, depending on the connectivity of \(H\) and the structure of \(G\) .