Compact Numerical Quadrature Formulas for Hypersingular Integrals and Integral Equations

In the first part of this work, we derive compact numerical quadrature formulas for finite-range integrals $I[f]=\int^{b}_{a}f(x)\,dx$ , where f(x)=g(x)|x?t| ^?? , ?? being real. Depending on the value of ??, these integrals are defined either in the regular sense or in the sense of Hadamard finite part. Assuming that g??C ^??[a,b], or g??C ^??(a,b) but can have arbitrary algebraic singularities at x=a and/or x=b, and letting h=(b?a)/n, n an integer, we derive asymptotic expansions for ${T}^{*}_{n}[f]=h\sum_{1\leq j\leq n-1,\ x_{j}\neq t}f(x_{j})$ , where x _j =a+jh and t??{x ₁,??,x _n?1}. These asymptotic expansions are based on some recent generalizations of the Euler?CMaclaurin expansion due to the author (A.?Sidi, Euler?CMaclaurin expansions for integrals with arbitrary algebraic endpoint singularities, in Math. Comput., 2012), and are used to construct our quadrature formulas, whose accuracies are then increased at will by applying to them the Richardson extrapolation process. We pay particular attention to the case in which ??=?2 and f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ , which arises in the context of periodic hypersingular integral equations. For this case, we propose the remarkably simple and compact quadrature formula $\widehat{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)-\pi^{2} g(t)h^{-1}$ , and show that $\widehat{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, and that it is exact for a class of singular integrals involving trigonometric polynomials of degree at most n. We show how $\widehat{Q}_{n}[f]$ can be used for solving hypersingular integral equations in an efficient manner. In the second part of this work, we derive the Euler?CMaclaurin expansion for integrals $I[f]=\int^{b}_{a} f(x)dx$ , where f(x)=g(x)(x?t) ^?? , with g(x) as before and ??=?1,?3,?5,??, from which suitable quadrature formulas can be obtained. We revisit the case of ??=?1, for which the known quadrature formula $\widetilde{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)$ satisfies $\widetilde{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, when f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ . We show that this formula too is exact for a class of singular integrals involving trigonometric polynomials of degree at most n?1. We provide numerical examples involving periodic integrands that confirm the theoretical results.     

Zur Konvergenz der Ableitungen von Interpolationspolynomen

Letp _n denote the polynomial of degreen or less that interpolates a given smooth functionf at the ?eby?ev nodest _j ⁿ =cos(jπ/n), 0≤j≤n, and let ‖·‖ be the maximum norm inC[?1, 1]. It is proved that fork-th derivatives (2≤k≤n) estimates of the following type hold $$\parallel f^{(k)} - p_n^{(k)} \parallel \leqslant c_k n^{k - 1} \inf \{ \parallel f^{(k)} - q\parallel :q \in \Pi _{n - k} \} .$$ In this relationc _k only depends onk andΠ _n?k denotes the space of polynomials up to degreen?k.     

Fine structure of a one-dimensional discrete point system

We consider a system of N points x ₁ < ... < x _N on a segment of the real line. An ideal system (crystal) is a system where all distances between neighbors are the same. Deviation from idealness is characterized by a system of finite differences ? _i ¹ = x _x+1 ? x _i , ? _i ^k+1 = ? _i+1 ^k ? ? _i ^k , for all possible i and k. We find asymptotic estimates as N ?? ??, k????, for a system of points minimizing the potential energy of a Coulomb system in an external field.     

Proper Interval Vertex Deletion

The NP-complete problem Proper Interval Vertex Deletion is to decide whether an input graph on n vertices and m edges can be turned into a proper interval graph by deleting at most k vertices. Van Bevern et al. (In: Proceedings WG 2010. Lecture notes in computer science, vol. 6410, pp. 232–243, 2010) showed that this problem can be solved in $\mathcal {O}((14k +14)^{k+1} kn^{6})$ time. We improve this result by presenting an $\mathcal {O}(6^{k} kn^{6})$ time algorithm for Proper Interval Vertex Deletion. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw,net,tent,C ₄,C ₅,C ₆}-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves Proper Interval Vertex Deletion on {claw,net,tent,C ₄,C ₅,C ₆}-free graphs in $\mathcal {O}(n+m)$ time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.     

Complexity-Theoretic Hierarchies Induced by Fragments of Gödel’s T

We introduce two hierarchies of unknown ordinal height. The hierarchies are induced by natural fragments of a calculus based on finite types and Gödel’s T, and all the classes in the hierarchies are uniformly defined without referring to explicit bounds. Deterministic complexity classes like logspace, p, pspace, linspace and exp are captured by the hierarchies. Typical subrecursive classes are also captured, e.g. the small relational Grzegorczyk classes ? _* ⁰ , ? _* ¹ and ? _* ² .     

Near-optimal bounded-degree spanning trees

Random costsC(i, j) are assigned to the arcs of a complete directed graph onn labeled vertices. Given the cost matrixC _n =(C(i, j)), letT* _k =T* _k (C _n ) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal tok. Since it is NP-hard to findT* _k , we instead consider an efficient algorithm that finds a near-optimal spanning treeT _k ^a . If the edge costs are independent, with a common exponential(I) distribution, then, asn → ∞, $$E(Cost(T_k^a {\text{)) = }}E(Cost(T_k^* {\text{)) + }}o\left( 1 \right).$$ Upper and lower bounds forE(Cost(T* _k )) are also obtained fork≥2.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).     

Analyses for L p [a, b]-norm approximation capability of flexible approximate identity neural networks

This study investigates the universal approximation capability of a three-layered feedforward flexible approximate identity neural networks under the L ^p [a, b]-norm. We are motivated to study such a problem by the fact that the L ^p [a, b]-norm has the capability of improving approximation performance significantly. Using flexible approximate identity functions as introduced in our previous study, we prove that any Lebesgue integrable function on the closed and bounded real interval [a, b] will converge to itself under the L ^p [a, b]-norm if it convolves with flexible approximate identity functions. Using this result, we also establish a main theorem. The proof of the main theorem is in the framework of the theory of $\epsilon$ -net.     

On Uniformity and Circuit Lower Bounds

We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts:

1. Lower bounds against medium-uniform circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex (stronger than LOGTIME) but not infeasible. Using a new kind of indirect diagonalization argument, we prove several new unconditional lower bounds against medium-uniform circuit classes, including: ? For all k, P is not contained in P-uniform SIZE(n ^k ). That is, for all k, there is a language \({L_k \in {\textsf P}}\) that does not have O(n ^k )-size circuits constructible in polynomial time. This improves Kannan’s lower bound from 1982 that NP is not in P-uniform SIZE(n ^k ) for any fixed k. ? For all k, NP is not in \({{\textsf P}^{\textsf NP}_{||}-{\textsf {uniform SIZE}}(n^k)}\) .This also improves Kannan’s theorem, but in a different way: the uniformity condition on the circuits is stronger than that on the language itself. ? For all k, LOGSPACE does not have LOGSPACE-uniform branching programs of size n ^k .
2. Eliminating non-uniformity and (non-uniform) circuit lower bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC ¹ in ACC ⁰/poly or TC ⁰/poly into a medium-uniform simulation using small advice. This lemma can be used to simplify the proof that faster SAT algorithms imply NEXP circuit lower bounds and leads to the following new connection: ? Consider the following task: given a TC ⁰ circuit C of n ^O(1) size, output yes when C is unsatisfiable, and output no when C has at least 2 ^n-2 satisfying assignments. (Behavior on other inputs can be arbitrary.) Clearly, this problem can be solved efficiently using randomness. If this problem can be solved deterministically in 2 ^n-ω(log n) time, then \({{\textsf{NEXP}} \not \subset {\textsf{TC}}^0/{\rm poly}}\) .

Another application is to derandomize randomized TC ⁰ simulations of NC ¹ on almost all inputs: ?Suppose \({{\textsf{NC}}^1 \subseteq {\textsf{BPTC}}^0}\) . Then, for every ε > 0 and every language L in NC ¹, there is a LOGTIME?uniform TC ⁰ circuit family of polynomial size recognizing a language L′ such that L and L′ differ on at most \({2^{n^{\epsilon}}}\) inputs of length n, for all n.     

An algorithm for division of powerseries

An algorithm is given to compute a solution (b ₀, ...,b _n) of $$\sum\limits_0^n {a_i t^i } \sum\limits_0^n {b_i t^i } \equiv \sum\limits_0^n {c_i t^i } (t^{n + 1} )$$ froma ₀, ..., a_n, c₀, ..., c_n. It needs less than 7n multiplications, where multiplications with a skalar from an infinite subfield are not counted.     

Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovi?, Acta Informatica 19:377?C384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a?+?b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275?C306, 2000) as well as Kondacs and Watrous (66?C75, 1997; Observe that 1-letter QFAs are exactly measure-once QFAs (MO-1QFAs) of Moore and Crutchfield (Theor Comput Sci 237:275?C306, 2000)). In this paper, we study the decidability of the equivalence and minimization problems of multi-letter QFAs. Three new results presented in this paper are the following ones: (1) Given a k ₁-letter QFA ${{\mathcal A}_1}$ and a k ₂-letter QFA ${{\mathcal A}_2}$ over the same input alphabet ??, they are equivalent if and only if they are (n ² m ^k-1?m ^k-1?+?k)-equivalent, where m =?|??| is the cardinality of ??, k =?max(k ₁,k ₂), and n =?n ₁?+?n ₂, with n ₁ and n ₂ being numbers of states of ${{\mathcal A}_{1}}$ and ${{\mathcal A}_{2}}$ , respectively. When k =?1, this result implies the decidability of equivalence of measure-once QFAs (Moore and Crutchfield in Theor Comput Sci 237:275?C306, 2000). (It is worth mentioning that our technical method is essentially different from the previous ones used in the literature.) (2) A polynomial-time O(m ^2k-1 n ⁸?+?km ^k n ⁶) algorithm is designed to determine the equivalence of any two multi-letter QFAs (see Theorems 2 and 3; Observe that if a brute force algorithm to determine equivalence would be used, as suggested by the decidability outcome of the point (1), the worst case time complexity would be exponential). Observe also that time complexity is expressed here in terms of the number of states of the multi-letter QFAs and k can be seen as a constant. (3) It is shown that the states minimization problem of multi-letter QFAs is solvable in EXPSPACE. This implies also that the state minimization problem of MO-1QFAs (see Moore and Crutchfield in Theor Comput Sci 237:275?C306, 2000, page 304, Problem 5), an open problem stated in that paper, is also solvable in EXPSPACE.     

Vertex Cover Kernelization Revisited

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G′,k′) in polynomial time with the guarantee that G′ has at most 2k′ vertices (and thus $\mathcal{O}((k')^{2})$ edges) with k′≤k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Θ(k ²) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number $\mathop{\mathrm{\mbox {\textsc{vc}}}}(G)$ since $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)\leq\mathop{\mathrm{\mbox{\textsc{vc}}}}(G)$ and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G′,X′,k′) such that |V(G′)|≤2k and $|V(G')| \in\mathcal{O}(|X'|^{3})$ . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP ? coNP/poly and the polynomial hierarchy collapses to the third level.     

A parametric algorithm for semigroup computation on mesh with buses

In this paper, we present a new parametric parallel algorithm for semigroup computation on mesh with reconfigurable buses (MRB). Givenn operands, our parallel algorithm can be performed in $O(2^{(2c^2 + 3c)/(4c + 1)} n^{1/(8c + 2)} )$ , time on a $2^{(c^2 - c)/(8c + 2)} n^{(5c + 1)/(8c + 2)} \times 2^{(c - c^2 )/(8c + 2)} n^{(3c + 1)/(8c + 2)} $ MRB ofn processors, where $0 \leqslant c \leqslant O(\sqrt {\log _2 n} )$ . Specifically, whenc=0, it takes $O(\sqrt n )$ time on the $\sqrt n \times \sqrt n $ MRB and is equal to the result on the mesh-connected computers; whenc=1, it takesO(n ^1/10) time on then ^3/5×n ^2/5 MRB and is equal to the previous result on the mesh-connected computers with segmented multiple buses; whenc=2, it takesO(n ^1/18) time on the 2^1/9 n ^11/18×2^(?1/9) n ^7/18 MRB; when $O(\sqrt {\log _2 n} )$ , it takesO(log₂ n) time and is equal to the previous result on the MRB. Consequently, our results can be viewed as a unification of some best known results on different parallel computational models.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

On the evaluation of one-dimensional Cauchy principal value integrals by rules based on cubic spline interpolation

In this note we consider the numerical evaluation of one dimensional Cauchy principal value integrals of the form $$\rlap{--} \smallint _a^b \frac{{k(x)f(x)}}{{x - \lambda }}dx, a< \lambda< b,$$ by rules obtained by “subtracting out” the singularity and then applying product quadratures based on cubic spline interpolation at equally spaced nodes. Convergence results are established for Hölder continuous functions of order, μ, 0<μ≤1, and asymptotic rates are obtained for functionsf≠C ^k [a, b],k=1, 2, 3 or 4. Some comparisons with other methods and numerical examples are also given.     

Erzeugende Funktionen bei Spline-Interpolation mit äquidistanten Knoten

Using generating functions we obtain in the case ofn+1 equidistant data points a method for the calculation of the interpolating spline functions(x) of degree 2k+1 with boundary conditionss ^(κ) (x₀)=y ₀ ^(κ) ,s ^(κ) (x _n )=y _n ^(κ) , κ=1(1)k, which only needs the inversion of a matrix of orderk. The applicability of our method in the case of general boundary conditions is also mentioned.     

Fixed-Parameter Tractability of Satisfying Beyond the Number of Variables

We consider a CNF formula F as a multiset of clauses: F={c ₁,…,c _m }. The set of variables of F will be denoted by V(F). Let B _F denote the bipartite graph with partite sets V(F) and F and with an edge between v∈V(F) and c∈F if v∈c or $\bar{v} \in c$ . The matching number ν(F) of F is the size of a maximum matching in B _F . In our main result, we prove that the following parameterization of MaxSat (denoted by (ν(F)+k)-SAT) is fixed-parameter tractable: Given a formula F, decide whether we can satisfy at least ν(F)+k clauses in F, where k is the parameter. A formula F is called variable-matched if ν(F)=|V(F)|. Let δ(F)=|F|?|V(F)| and δ ^?(F)=max _F′?F δ(F′). Our main result implies fixed-parameter tractability of MaxSat parameterized by δ(F) for variable-matched formulas F; this complements related results of Kullmann (IEEE Conference on Computational Complexity, pp. 116–124, 2000) and Szeider (J. Comput. Syst. Sci. 69(4):656–674, 2004) for MaxSat parameterized by δ ^?(F). To obtain our main result, we reduce (ν(F)+k)-SAT into the following parameterization of the Hitting Set problem (denoted by (m?k)-Hitting Set): given a collection $\mathcal{C}$ of m subsets of a ground set U of n elements, decide whether there is X?U such that C∩X≠? for each $C\in \mathcal{C}$ and |X|≤m?k, where k is the parameter. Gutin, Jones and Yeo (Theor. Comput. Sci. 412(41):5744–5751, 2011) proved that (m?k)-Hitting Set is fixed-parameter tractable by obtaining an exponential kernel for the problem. We obtain two algorithms for (m?k)-Hitting Set: a deterministic algorithm of runtime $O((2e)^{2k+O(\log^{2} k)} (m+n)^{O(1)})$ and a randomized algorithm of expected runtime $O(8^{k+O(\sqrt{k})} (m+n)^{O(1)})$ . Our deterministic algorithm improves an algorithm that follows from the kernelization result of Gutin, Jones and Yeo (Theor. Comput. Sci. 412(41):5744–5751, 2011).     

Contracting Graphs to Paths and Trees

Vertex deletion and edge deletion problems play a central role in parameterized complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain a tree or a path, respectively, by a sequence of at most k edge contractions in G. For Tree Contraction, we present a randomized 4 ^k ? n ^O(1) time polynomial-space algorithm, as well as a deterministic 4.98 ^k ? n ^O(1) time algorithm, based on a variant of the color coding technique of Alon, Yuster and Zwick. We also present a deterministic 2 ^k+o(k)+n ^O(1) time algorithm for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most 5k+3 vertices, while Tree Contraction does not have a polynomial kernel unless NP ? coNP/poly. We find the latter result surprising because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with 4k ² vertices.     

Spin-spin interaction in general relativity and induced geometries with nontrivial topology

We consider the dynamics of a self-gravitating spinor field and a self-gravitating rotating perfect fluid. It is shown that both these matter distributions can induce a vortex field described by the curl 4-vector of a tetrad: θ ⁱ = ½ε ^iklm e _(a)k e _l;m ^(a) , where e _k ^(a) are components of the tetrad. The energy-momentum tensor T _ik (ω) of this field has been found and shown to violate the strong and weak energy conditions which leads to possible formation of geometries with nontrivial topology like wormholes. The corresponding exact solutions to the equations of general relativity have been found. It is also shown that other vortex fields, e.g., the magnetic field, can also possess such properties.     

Properties of interval operators

In this paper we give some properties of interval operatorsF which guarantee the convergence of the interval sequence {X _k} defined byX _k+1:=F(X_k)∩X_k to a unique fixed interval \(\hat X\) . This interval \(\hat X\) encloses the “zero-set”X ^* of a function strip \(G(x): = [g(x),\bar g(x)]\) . for some known interval operators we investigate under which assumptions these properties are valid.