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.     

Formule di quadratura «chiuse» di tipo gaussiano: Tabulzione dei nodi e dei coefficienti

The coefficientsA _hi and the nodesx _mi for «closed” Gaussian-type quadrature formulae $$\int\limits_{ - 1}^1 {f(x)dx = \sum\limits_{h = 0}^{2_8 } {\sum\limits_{i = 0}^{m + 1} {A_{hi} f^{(h)} (x_{mi} ) + R\left[ {f(x)} \right]} } } $$ withx _m0 =?1,x _{m, m+1} =1 andR[f(x)]=0 iff(x) is a polinomial of degree at most2m(s+1)+2(2s+1)?1, have been tabulated for the cases: $$\left\{ \begin{gathered} s = 1,2 \hfill \\ m = 2,3,4,5 \hfill \\ \end{gathered} \right.$$ .     

On the computation of Tricomi's ψ function

Two methods for calculating Tricomi's confluent hypergeometric function are discussed. Both methods are based on recurrence relations. The first method converges like $$\exp ( - \alpha |\lambda |^{1/3} n^{2/3} )for some \alpha > 0$$ and the second like $$\exp ( - \beta |\lambda |^{1/2} n^{1/2} )for some \beta > 0.$$ Several examples are presented.     

Sulle formule di quadratura di Tschebyscheff

For the Tschebyscheff quadrature formula: $$\int\limits_{ - 1}^1 {\left( {1 - x^2 } \right)^{\lambda - 1/2} f(x) dx} = K_n \sum\limits_{k = 1}^n {f(x_{n,k} )} + R_n (f), \lambda > 0$$ it is shown that the degre,N, of exactness is bounded by: $$N \leqslant C(\lambda )n^{1/(2\lambda + 1)} $$ whereC(λ) is a convenient function of λ. For λ=1 the complete solution of Tschebyscheff's problem is given.     

Numerical evaluation of a solution of a special mixed-type differential-difference equation

The function * $$f(t) = \frac{{e^{ - \alpha \gamma } }}{\pi }\int\limits_0^\infty {\cos t \xi e^{\alpha Ci(\xi )} \frac{{d\xi }}{{\xi ^\alpha }},t \in R,\alpha > 0} $$ [Ci(x)=cosine integral, γ=Euler's constant] is studied and numerically evaluated;f is a solution to the following mixed type differential-difference equation arising in applied probability: ** $$tf'(t) = (\alpha - 1)f(t) - \frac{\alpha }{2}[f(t - 1) + f(t + 1)]$$ satisfying the conditions: i) $$f(t) \geqslant 0,t \in R$$ , ii) $$f(t) = f( - t),t \in R$$ , iii) $$\int\limits_{ - \infty }^{ + \infty } {f(\xi )d\xi = 1} $$ . Besides the direct numerical evaluation of (*) and the derivation of the asymptotic behaviour off(t) fort→0 andt→∞, two different iterative procedures for the solution of (**) under the conditions (i) to (iii) are considered and their results are compared with the corresponding values in (*). Finally a Monte Carlo method to evaluatef(t) is considered.     

The addition of bounded quantification and partial functions to a computational logic and its theorem prover

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects in the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as ‘mapping functions’. The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as ‘capturing’, ‘bottom’, or ‘continuity’. Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are:

? classic quantifier manipulation theorems, such as $$\sum\limits_{{\text{l}} = 0}^{\text{n}} {{\text{g}}({\text{l}}) + {\text{h(l) = }}} \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{g}}({\text{l}})} + \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{h(l)}};} $$

? elementary theorems involving quantifiers, such as the Binomial Theorem: $$(a + b)^{\text{n}} = \sum\limits_{{\text{l = }}0}^{\text{n}} {\left( {_{\text{i}}^{\text{n}} } \right)} \user2{ }{\text{a}}^{\text{l}} {\text{b}}^{{\text{n - l}}} ;$$

? elementary theorems about ‘mapping functions’ such as: $$(FOLDR\user2{ }'PLUS\user2{ O L) = }\sum\limits_{{\text{i}} \in {\text{L}}}^{} {{\text{i}};} $$

? termination properties of many partial recursive functions such as the fact that an application of the partial function described by $$\begin{gathered} (LEN X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F ({\rm E}QUAL X NIL) \hfill \\ {\rm O} \hfill \\ (ADD1 (LEN (CDR X)))) \hfill \\ \end{gathered} $$ terminates if and only if the argument ends in NIL;

? theorems about functions satisfying unusual recurrence equations such as the 91-function and the following list reverse function: $$\begin{gathered} (RV X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F (AND (LISTP X) (LISTP (CDR X))) \hfill \\ (CONS (CAR (RV (CDR X))) \hfill \\ (RV (CONS (CAR X) \hfill \\ (RV (CDR (RV (CDR X))))))) \hfill \\ X). \hfill \\ \end{gathered} $$

     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

The exact region of stability for MacCormack scheme

Let the two dimensional scalar advection equation be given by $$\frac{{\partial u}}{{\partial t}} = \hat a\frac{{\partial u}}{{\partial x}} + \hat b\frac{{\partial u}}{{\partial y}}.$$ We prove that the stability region of the MacCormack scheme for this equation isexactly given by $$\left( {\hat a\frac{{\Delta _t }}{{\Delta _x }}} \right)^{2/3} + \left( {\hat b\frac{{\Delta _t }}{{\Delta _x }}} \right)^{2/3} \leqslant 1$$ where Δ _t , Δ _x and Δ _y are the grid distances. It is interesting to note that the stability region is identical to the one for Lax-Wendroff scheme proved by Turkel.     

On the Exact Complexity of Evaluating Quantified k -CNF

We relate the exponential complexities 2 ^s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 ^cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma.     

Modifikationen des Pollard-Algorithmus

The factorization algorithm of Pollard generates a sequence in ? _n by $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ wheren denotes the integer to be factored. The algorithm finds an factorp ofn within \(0\left( {\sqrt p } \right)\) macrosteps (=multiplications/divisions in ? _n ) on average. An empirical analysis of the Pollard algorithm using modified sequences $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ withx ₀,b,c,α∈? and α≥2 shows, that a factorp ofn under the assumption gcd (α,p-1)≠1 now is found within $$0\left( {\sqrt {\frac{p}{{ged(\alpha ,p - 1}}} } \right)$$ macrosteps on average.     

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.     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

On the class of λ-statistically convergent difference sequences of fuzzy numbers

In this study, we introduce the sets $\left[ V,\lambda ,p\right] _{\Updelta }^{{\mathcal{F}}},\left[ C,1,p\right] _{\Updelta }^{{\mathcal{F}}}$ and examine their relations with the classes of $ S_{\lambda }\left( \Updelta ,{\mathcal{F}}\right)$ and $ S_{\mu }\left( \Updelta ,{\mathcal{F}}\right)$ of sequences for the sequences $\left( \lambda _{n}\right)$ and $\left( \mu _{n}\right) , 0<p<\infty $ and difference sequences of fuzzy numbers.     

Alcuni problemi relativi alle formule di quadratura del tipo di tchebycheff

In this paper we study quadrature formulas of the form $$\int\limits_{ - 1}^1 {(1 - x)^a (1 + x)^\beta f(x)dx = \sum\limits_{i = 0}^{r - 1} {[A_i f^{(i)} ( - 1) + B_i f^{(i)} (1)] + K_n (\alpha ,\beta ;r)\sum\limits_{i = 1}^n {f(x_{n,i} ),} } } $$ (α>?1, β>?1), with realA _i ,B _i ,K _n and real nodesx _n,i in (?1,1), valid for prolynomials of degree ≤2n+2r?1. In the first part we prove that there is validity for polynomials exactly of degree2n+2r?1 if and only if α=β=?1/2 andr=0 orr=1. In the second part we consider the problem of the existence of the formula $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} f(x)dx = A_n f( - 1) + B_n f(1) + C\sum\limits_{i = 1}^n {f(x_{n,i} )} }$$ for polynomials of degree ≤n+2. Some numerical results are given when λ=1/2.     

Caratteristiche numeriche della forma integrale delle equazioni differenziali di ordineN

A numerical performance of integral form for the linear ordinary differential equations $$y^{(n)} = \sum\limits_{i = 0}^{n - 2} { a_{i + 2} (x) y^{(n - 2 - i)} (x)}$$ is proved. Three numerical experiments are also given.     

Delayed theory combination vs. Nelson-Oppen for satisfiability modulo theories: a comparative analysis

Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ .