Radial Basis Function generated Finite Differences for option pricing problems

In this paper we present a numerical method to price options based on Radial Basis Function generated Finite Differences (RBF-FD) in space and the Backward Differentiation Formula of order 2 (BDF-2) in time. We use Gaussian RBFs that depend on a shape parameter $\epsilon$. The choice of this parameter is crucial for the performance of the method. We chose $\epsilon$ as $\mathrm{const}?h^{?1}$ and we derive suitable values of the constant for different stencil sizes in 1D and 2D. This constant is independent of the problem parameters such as the volatilities of the underlying assets and the interest rate in the market. In the literature on option pricing with RBF-FD, a constant value of the shape parameter is used. We show that this always leads to ill-conditioning for decreasing $h$, whereas our proposed method avoids such ill-conditioning. We present numerical results for problems in 1D, 2D, and 3D demonstrating the useful features of our method such as discretization sparsity, flexibility in node placement, and easy dimensional extendability, which provide high computational efficiency and accuracy.     

Testing hypergraph colorability

We study the problem of testing properties of hypergraphs. The goal of property testing is to distinguish between the case whether a given object has a certain property or is “far away” from the property. We prove that the fundamental problem of $\ell$-colorability of k-uniform hypergraphs can be tested in time independent of the size of the hypergraph. We present a testing algorithm that examines only $(k\ell /\epsilon {)}^{\mathrm{O}(k)}$ entries of the adjacency matrix of the input hypergraph, where $\epsilon$ is a distance parameter independent of the size of the hypergraph. The algorithm tests only a constant number of entries in the adjacency matrix provided that $\ell$, k, and $\epsilon$ are constants. This result is a generalization of previous results about testing graph colorability.     

Hardness of approximating the Shortest Vector Problem in high ℓp norms

We present a new hardness of approximation result for the Shortest Vector Problem in ${\ell }_p$ norm (denoted by ${\mathrm{SVP}}_p$). Assuming NP $⊈$ ZPP, we show that for every $\epsilon >0$, there is a constant $p(\epsilon )$ such that for all integers $p⩾p(\epsilon )$, the problem ${\mathrm{SVP}}_p$ has no polynomial time approximation algorithm with approximation ratio $p^{1-\epsilon }$.     

Fractional Wishart processes and ε-fractional Wishart processes with applications

In this paper, we introduce two new matrix stochastic processes: fractional Wishart processes and $\epsilon$-fractional Wishart processes with integer indices which are based on the fractional Brownian motions and then extend $\epsilon$-fractional Wishart processes to the case with non-integer indices. Both processes include classic Wishart processes (if the Hurst index $H$ equals $\frac{1}{2}$) and present serial correlation of stochastic processes. Applying $\epsilon$-fractional Wishart processes to financial volatility theory, the financial models account for the stochastic volatilities of the assets and for the stochastic correlations not only between the underlying assets’ returns but also between their volatilities and for stochastic serial correlation of the relevant assets.     

A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in $1,\dots ,M$, it runs in $\stackrel{?}{O}(\sqrt{M}{n}^{(\omega +3)/2})$ time where $\omega <2.376$ is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in $\stackrel{?}{O}(M{n}^{\omega }t)$ time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in $\stackrel{?}{O}(n^{(\omega +6)/3})$ time.     

Information transmittal,relativity and gravitation

Special relativity considered in [Albert Einstein, Zur Elektrodynamik der bewegte Körper, Ann. Phys. 17 (1905) 891–921], and gravitation, studied in a series of papers, notably in [Albert Einstein, Zum gegenwärtigen Stände des Gravitationsproblemen, Phys. Z. 14 (1913) 1249–1262], are further analyzed regarding the principle of relativity, gravitation, and the notion of mass. The energy relation derived by Einstein from the relativistic Maxwell equations is applied to potential energy $W\left(x\right)$ of the gravitational field along the right line for which Einstein’s transformations are valid. This defines the intensity $G\left(x\right)=dW/dx$ of the relativistic force of gravity along a right line of observation in the gravitational field. The force is proportional to the observed acceleration according to the formula $\epsilon G\left(x\right)=\mu {\xi }_{\tau \tau }=\mu x_{tt}{\beta }^3$ where $\mu$ is the inert mass in the second Newton’s law of motion and $\epsilon$ is the charge (mass) in the relativistic electromagnetic (gravitational) field. In everyday life, we see that all bodies visually fall under gravity (i.e. in a common gravitational field) with the same observed acceleration ${\xi }_{\tau \tau }$ as if having equal inert and gravitational masses: $\mu /\epsilon =1$, with respect to the synchronized time $\tau$. However, if the principle of relativity extended by Einstein to the case of the uniformly accelerated rectilinear motion is valid, then this relation should also be true with respect to $x_{tt}$, that is, $(\mu /\epsilon ){\beta }^3=1$, in proper time $t$ of a still observer and of the carrying system (falling body), thus, depending on velocity $v$ at which the acceleration ${\xi }_{\tau \tau }$ is measured. This means that the inert mass $\mu$ and the gravitational mass $\epsilon$ can be considered equal only at $v=0$, and otherwise are related by the equation $\epsilon =\mu {\beta }^3\ge \mu$, where Einstein’s calibration factor $\beta ={[1?{(v/V)}^2]}^{?0.5}\ge 1,\left|v\right|<V$, and $\beta ?1$ for small $\left|v\right|$ compared with the speed of light $V=300000\mathrm{km/s}$ at which we see the falling bodies. If $v>0$, then the observed gravitational mass $\epsilon$ is greater than the inert mass $\mu$. The increase of mass is concurrent with the increase of tensions that at high velocities $v\to V$ induce overheating in the particle accelerators and colliders. To comply with the nature of observation, the information transmittal signals are incorporated in the Lorentz invariant of the $4D$ geometry, leading to the local invariants of relativistic dynamics that include gravitation and the speed of signals used in observation of moving bodies. With the same communication signals, those invariants hold for the synchronized time and coordinates of moving systems irrespective of their relative velocities. A procedure is developed for measurement and computation of the accelerations produced by variable gravitational and/or electromagnetic fields through the measurements of velocities of a moving body, so that the motion of the body and the field of forces acting on it can be fully identified. The results open new avenues for research in the theory of relativity and its applications.     

A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities

This paper describes a direct solver algorithm for a sequence of finite element meshes that are $h$-refined towards one or several point singularities. For such a sequence of grids, the solver delivers linear computational cost $O\left(N\right)$ in terms of CPU time and memory with respect to the number of unknowns $N$. The linear computational cost is achieved by utilizing the recursive structure provided by the sequence of $h$-adaptive grids with a special construction of the elimination tree that allows for reutilization of previously computed partial LU (or Cholesky) factorizations over the entire unrefined part of the computational mesh. The reutilization technique reduces the computational cost of the entire sequence of $h$-refined grids from $O\left(N^2\right)$ down to $O\left(N\right)$. Theoretical estimates are illustrated with numerical results on two- and three-dimensional model problems exhibiting one or several point singularities.     

Swapped interconnection networks: Topological,performance, and robustness attributes

Interconnection architectures range from complete networks, that have a diameter of $D=1$ but are impractical except when the number $n$ of nodes is small, to low-cost, minimally connected ring networks whose diameter $D=\lfloor n/2\rfloor$ is unacceptable for large $n$. In this paper, our focus is on swapped interconnection networks that allow systematic construction of large, scalable, modular, and robust parallel architectures, while maintaining many desirable attributes of the underlying basis network comprising its clusters. A two-level swapped network with $n^2$ nodes is built of $n$ copies of an $n$-node basis network using a simple rule for intercluster connectivity (node $j$ in cluster $i$ connected to node $i$ in cluster $j$) that ensures its regularity, modularity, packageability, fault tolerance, and algorithmic efficiency. We show how key parameters of a swapped interconnection network are related to the corresponding parameters of its basis network and discuss implications of these results to synthesizing large networks with desirable topological, performance, and robustness attributes. In particular, we prove that a swapped network is Hamiltonian (respectively, Hamiltonian-connected) if its basis network is Hamiltonian (Hamiltonian-connected). These general results supersede a number of published results for specific basis networks and obviate the need for proving Hamiltonicity or Hamiltonian connectivity for many other basis networks of practical interest.     

A note on asynchronous multi-exponentiation algorithm using binary representation

A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-exponentiation in a certain finite multiplication group. In 2007, Yang et al. presented an interesting asynchronous multi-exponentiation algorithm called the ${\mathit{SU}}_t$ method, which uses the binary representations for the exponents. In this note, we analyze the computational efficiency of the ${\mathit{SU}}_t$ method by modeling the scanning process as a Markov chain. It shows that their computational efficiency result is incorrect. Moreover, we make a performance comparison among the published techniques and show that the performance of a modified sliding window method is better than that of the ${\mathit{SU}}_t$ method, when there are 4 or more additional registers. We hope that our research will be convenient to the development of the cryptographic devices.