Approximate Option Pricing

As increasingly large volumes of sophisticated options are traded in world financial markets, determining a ``fair' price for these options has become an important and difficult computational problem. Many valuation codes use the binomial pricing model, in which the stock price is driven by a random walk. In this model, the value of an n -period option on a stock is the expected time-discounted value of the future cash flow on an n -period stock price path. Path-dependent options are particularly difficult to value since the future cash flow depends on the entire stock price path rather than on just the final stock price. Currently such options are approximately priced by Monte Carlo methods with error bounds that hold only with high probability and which are reduced by increasing the number of simulation runs. In this article we show that pricing an arbitrary path-dependent option is \#-P hard. We show that certain types of path-dependent options can be valued exactly in polynomial time. Asian options are path-dependent options that are particularly hard to price, and for these we design deterministic polynomial-time approximate algorithms. We show that the value of a perpetual American put option (which can be computed in constant time) is in many cases a good approximation of the value of an otherwise identical n -period American put option. In contrast to Monte Carlo methods, our algorithms have guaranteed error bounds that are polynomially small (and in some cases exponentially small) in the maturity n . For the error analysis we derive large-deviation results for random walks that may be of independent interest. Received August 13, 1996; revised April 2, 1997.     

A Dynamic Model of Cracks Development Based on a 3D Discrete Shrinkage Volume Propagation

We attempt to model and visualize the main characteristics of cracks produced on the surface of a desiccating crusted soil: their patterns, their different widths and depths and their dynamics of creation and evolution. In this purpose we propose a method to dynamically produce three‐dimensional (3D) quasi‐static fractures, which takes into account the characteristics of the soil. The main originality of this method is the use of a 3D discrete propagation of ‘shrinkage volumes’ with respect to 2D precalculated paths. In order to get realistic cracks, we newly propose to take into account a possibly inhomogeneous thickness of the shrinking layer by using a watershed transformation to compute these paths. Moreover, we use the waterfall algorithm in order to introduce in our simulation a hierarchy notion in the cracks appearance, which is therefore linked with the initial structure of the surface. In this paper, this method is presented in detail and a validation of the cracks patterns by a comparison with real ones is given.     

An efficient parallel mixed method for flow simulations in heterogeneous geological media

The permeability of a 3D geological fracture network is determined by triangulating the fractures and solving the 2D Darcy's equation in each fracture. Here, the numerical modelling aims to simulate a great number of networks made up of a great number of fractures i.e. from 10³ to 10⁶ fractures. Parallel computing allows us to solve very large linear systems improving the realism of simulations. Several algorithms to simulating fluid flow are proposed for the cases of significant matrix permeability. In the case of a weak permeability matrix, the flow is focused in the fractures having a strong permeability and fluids percolate through networks of interconnected fractures. In this paper, we present a complete parallel algorithm for solving flow equations in fracture networks. We consider an imprevious matrix. The different parts of the algorithm are detailed. Numerical examples using the mixed finite element (MFE) method for various fracture networks illustrate the efficiency and robustness of the proposed algorithm. To the best of our knowledge, results for parellel simulation of fluid flow in discrete-fractured media with impervious matrix using the MFE method are the first to appear in the literature.     

On the equal-weight symmetric Boolean functions

Two important classes of symmetric Boolean functions are the equal-weight Boolean functions and the elementary (or homogeneous) symmetric Boolean functions. In this paper we studied the equal-weight symmetric Boolean functions. First the Walsh spectra of the equal-weight symmetric Boolean functions are given. Second the sufficient and necessary condition on correlation-immunity of the equal-weight symmetric Boolean function is derived and other cryptology properties such as the nonlinearity, balance and propagation criterion are taken into account. In particular, the nonlinearity of the equal-weight symmetric Boolean functions with n (n ≥ 10) variables is determined by their Hamming weight. Considering these properties will be helpful in further investigations of symmetric Boolean functions.     

THERMIC: a 2-D finite-element tool to solve conductive and advective heat transfer problems in Earth Sciences

We present a C-language program, THERMIC, that solves the 2-dimensional (pseudo 3D for axi-symmetric cases) conductive and advective heat-transfer equation. THERMIC uses a finite-element method that takes into account realistic geometries, heterogeneous material properties and various boundary and initial conditions. As it also allows for latent heat (heat production due to crystallisation) and for thermal properties, such as thermal conductivity, to be dependent on temperature, it is particularly suited to heat transfer problems encountered in the Earth Sciences. We present sample applications from the various problems already treated by THERMIC (cooling of magma chambers and dykes, the study of a granitic magma ascent or of pore water flow in sedimentary basins).Successfully tested on SUN® and SGI® UNIX workstations and on Microsoft Windows 95®, 98® and NT® 4.0 system based PCs, the THERMIC package can be downloaded from the web (THERMIC home page: http://www.ipgp.jussieu.fr/UFP/thermic/html/Thermic_home.html) and contains source files, makefiles and environment files as well as executable files for both systems and an html directory with help and example files.     

Dynamic fractional cascading

The problem of searching for a key in many ordered lists arises frequently in computational geometry. Chazelle and Guibas recently introduced fractional cascading as a general technique for solving this type of problem. In this paper we show that fractional cascading also supports insertions into and deletions from the lists efficiently. More specifically, we show that a search for a key inn lists takes timeO(logN +n log logN) and an insertion or deletion takes timeO(log logN). HereN is the total size of all lists. If only insertions or deletions have to be supported theO(log logN) factor reduces toO(1). As an application we show that queries, insertions, and deletions into segment trees or range trees can be supported in timeO(logn log logn), whenn is the number of segments (points).This research was supported by the Deutsche Forschungsgemeinschaft under Grants Me 620/6-1 and SFB 124, Teilprojekt B2. A preliminary version of this research was presented at the ACM Symposium on Computational Geometry, Baltimore, 1985.     

All-pole phase-locked loops: calculating lock-in range by using Evan's root-locus

The dynamics of a phase-locked loop (PLL), an essential component for the electronic synchronization processes, is described by an ordinary nonlinear differential equation with an order equal to 1 plus the order of its internal linear low-pass filter. Literature contains several results mainly concerned to the second-order loops giving expressions for lock-in range and transient response specifying a linear equivalent second-order system. However, in some applications, more accurate transient responses are necessary and the PLL performance can be improved by considering the higher-order filters resulting in the nonlinear loops with order greater than 2. Such systems, due to high order and nonlinear terms, depending on the parameters combination can present some undesirable behaviors, resulting from bifurcations, as error oscillation and chaos, decreasing the synchronization ranges. Implication to engineering design is that some regions of the parameter space become forbidden limiting the circuit options. This work is a contribution on establishing the lock-in range for a PLL of generic order n?+?1, considering that the filter is all-pole linear stable low-pass of order n. Analysis is performed by detecting a Hopf bifurcation on the synchronous state by using the root-locus method combined with the dynamical system theory. The lock-in range is calculated by applying the classical control tools defining an equivalent feedback control system.     

Fractional differential approach to detecting textural features of digital image and its fractional differential filter implementation

This paper mainly discusses fractional differential approach to detecting textural features of digital image and its fractional differential filter. Firstly, both the geo- metric meaning and the kinetic physical meaning of fractional differential are clearly explained in view of information theory and kinetics, respectively. Secondly, it puts forward and discusses the definitions and theories of fractional stationary point, fractional equilibrium coefficient, fractional stable coefficient, and fractional grayscale co-occurrence matrix. At the same time, it particularly discusses frac- tional grayscale co-occurrence matrix approach to detecting textural features of digital image. Thirdly, it discusses in detail the structures and parameters of nxn any order fractional differential mask on negative x-coordinate, positive x-coordi- nate, negative y-coordinate, positive y-coordinate, left downward diagonal, left upward diagonal, right downward diagonal, and right upward diagonal, respectively. Furthermore, it discusses the numerical implementation algorithms of fractional differential mask for digital image. Lastly, based on the above-mentioned discus- sion, it puts forward and discusses the theory and implementation of fractional differential filter for digital image. Experiments show that the fractional differential-based image operator has excellent feedback for enhancing the textural details of rich-grained digital images.     

The h‐Difference Approach to Controllability and Observability of Fractional Linear Systems with Caputo–Type Operator

In the paper a class of h‐difference linear control systems with n fractional orders is studied. The Caputo‐type h‐difference operator is used. The formula of the solution to the stated initial value problem of the given system is proved. The problems of controllability and observability in a finite number of steps of h‐difference linear control systems with n fractional orders are studied.     

Image denoising algorithm based on the convolution of fractional Tsallis entropy with the Riesz fractional derivative

Image denoising is an important component of image processing. The interest in the use of Riesz fractional order derivative has been rapidly growing for image processing recently. This paper mainly introduces the concept of fractional calculus and proposes a new mathematical model in using the convolution of fractional Tsallis entropy with the Riesz fractional derivative for image denoising. The structures of n × n fractional mask windows in the x and y directions of this algorithm are constructed. The image denoising performance is assessed using the visual perception, and the objective image quality metrics, such as peak signal-to-noise ratio (PSNR), and structural similarity index (SSIM). The proposed algorithm achieved average PSNR of 28.92 dB and SSIM of 0.8041. The experimental results prove that the improvements achieved are compatible with other standard image smoothing filters (Gaussian, Kuan, and Homomorphic Wiener).

     

On the Maximum Noninteger Polyhedron Vertices of the Three-index Axial Assignment Problem

Consideration was given to the maximum noninteger polyhedron vertices in the three-index axial assignment problem of the order n, that is, vertices with 3n - 2 fractional components. New types of these vertices were specified and their combinatorial characteristics studied.     

Democratic group signatures with collective traceability

Recently, democratic group signatures (DGSs) particularly catch our attention due to their great functionalities, i.e., no group manager, anonymity, and individual traceability. In existing DGS schemes, individual traceability says that any member in the group can reveal the actual signer’s identity from a given signature. In this paper, we strengthen the security notions of DGS by taking insider attack against anonymity into account, and present a concrete DGS construction with collective traceability. The idea behind collective traceability is that a sender can first choose (ad-hoc) a set of n members (including himself), and then sign a message by using the public keys of all the members, in such a way that his identity would be recovered, in case of disputes, if and only if all n members collectively cooperate. The security properties of our scheme are formally proved under reasonable assumptions.     

A Classification of Time and/or Probability Dependent Security Properties

In multilevel systems it is important to avoid unwanted indirect information flow from higher levels to lower levels, namely the so called covert channels. Initial studies of information flow analysis were performed by abstracting away from time and probability. It is already known that systems that are considered to be secure may turn out to be insecure when time or probability are considered. Recently, work has been done in order to consider also aspects either of time or of probability, but not both. In this paper we propose a general framework, based on Probabilistic Timed Automata, where both probabilistic and timing covert channels can be studied. We define a Non-Interference security property that allows one to express information flow in a timed and probabilistic setting, and we compare the property with analogous properties defined in settings where either time or probability or none of them are taken into account. This allows to classify properties depending on their discerning power.     

Minimal realisations of odd transfer functions for first-degree nD systems

ABSTRACT

Minimal realisation problems of odd transfer functions for first-degree (multi-linear) nD single-input single-output discrete systems have been studied, but it has not been well solved. This paper provides a new, different method to solve absolutely minimal realisation problems. By methods of limits and algebraic techniques, without using the symbolic approach by Gröbner basis, the requirements of absolutely minimal realisation are transformed into a system of equations represented by the determinants. Since the equations for first-degree 2D systems are solvable by quadratic equations and the conditions for higher-dimensional realisations can be expressed by the results of 2D systems, the absolutely minimal realisations for nD systems can be found by using the realisations of n(n ? 1)/2 2D systems. Furthermore, the conditions for existence and construction of the absolutely minimal realisation for the lack of items and not missing two cases are derived from the Pfaffian function of the skew-symmetric matrix. Finally, two numerical examples for 3D and 4D systems are presented to illustrate the basic ideas as well as the effectiveness of the proposed procedure.     

Relativistic Effects for Time‐Resolved Light Transport

We present a real‐time framework which allows interactive visualization of relativistic effects for time‐resolved light transport. We leverage data from two different sources: real‐world data acquired with an effective exposure time of less than 2 picoseconds, using an ultra‐fast imaging technique termed femto‐photography, and a transient renderer based on ray‐tracing. We explore the effects of time dilation, light aberration, frequency shift and radiance accumulation by modifying existing models of these relativistic effects to take into account the time‐resolved nature of light propagation. Unlike previous works, we do not impose limiting constraints in the visualization, allowing the virtual camera to explore freely a reconstructed 3D scene depicting dynamic illumination. Moreover, we consider not only linear motion, but also acceleration and rotation of the camera. We further introduce, for the first time, a pinhole camera model into our relativistic rendering framework, and account for subsequent changes in focal length and field of view as the camera moves through the scene.     

The Riemannian Geometry of the Space of Positive-Definite Matrices and Its Application to the Regularization of Positive-Definite Matrix-Valued Data

In this paper we present a Riemannian framework for smoothing data that are constrained to live in P(n)\mathcal{P}(n), the space of symmetric positive-definite matrices of order n. We start by giving the differential geometry of P(n)\mathcal{P}(n), with a special emphasis on P(3)\mathcal{P}(3), considered at a level of detail far greater than heretofore. We then use the harmonic map and minimal immersion theories to construct three flows that drive a noisy field of symmetric positive-definite data into a smooth one. The harmonic map flow is equivalent to the heat flow or isotropic linear diffusion which smooths data everywhere. A modification of the harmonic flow leads to a Perona-Malik like flow which is a selective smoother that preserves edges. The minimal immersion flow gives rise to a nonlinear system of coupled diffusion equations with anisotropic diffusivity. Some preliminary numerical results are presented for synthetic DT-MRI data.     

An open source, parallel DSMC code for rarefied gas flows in arbitrary geometries

This paper presents the results of validation of an open source Direct Simulation Monte Carlo (DSMC) code for general application to rarefied gas flows. The new DSMC code, called dsmcFoam, has been written within the framework of the open source C++ CFD toolbox OpenFOAM. The main features of dsmcFoam code include the capability to perform both steady and transient solutions, to model arbitrary 2D/3D geometries, and unlimited parallel processing. Test cases have been selected to cover a wide range of benchmark examples from 1D to 3D. These include relaxation to equilibrium, 2D flow over a flat plate and a cylinder, and 3D supersonic flows over complex geometries. In all cases, dsmcFoam shows very good agreement with data provided by both analytical solutions and other contemporary DSMC codes.     

Novel e-nose for the discrimination of volatile organic biomarkers with an array of carbon nanotubes (CNT) conductive polymer nanocomposites (CPC) sensors

We report the original design of a new type of electronic nose (e-nose) consisting of only five sensors made of hierarchically structured conductive polymer nanocomposites (CPC). Each sensor benefits from both the exceptional electrical properties of carbon nanotubes (CNT) used to build the conductive architecture and the spray layer by layer (sLbL) assembly technique, which provides the transducers with a highly specific 3D surface structure. Excellent sensitivity and selectivity were obtained by optimizing the amount of CNT with five different polymer matrices: poly(caprolactone) (PCL), poly(lactic acid) (PLA), poly(carbonate) (PC), poly(methyl methacrylate) (PMMA) and a biobased polyester (BPR). The ability of the resulting e-nose to detect nine organic solvent vapours (isopropanol, tetrahydrofuran, dichloromethane, n-heptane, cyclohexane, methanol, ethanol, water and toluene), as well as biomarkers for lung cancer detection in breath analysis, has been demonstrated. Principal component analysis (PCA) proved to be an excellent pattern recognition tool to separate vapour clusters.     

Research on Fractional Critical Covered Graphs

A graph G is called a fractional (g, f)-covered graph if for any e ∈ E(G), G admits a fractional (g, f)-factor covering e. A graph G is called a fractional (g, f, n)-critical covered graph if for any S ? V(G) with ∣S∣ = n, G ? S is a fractional (g, f)-covered graph. A fractional (g, f, n)-critical covered graph is said to be a fractional (a, b, n)-critical covered graph if g(x) = a and f(x) = b for every x ∈ V(G). A fractional (a, b, n)-critical covered graph was first defined and studied in [1]. In this article, we investigate fractional (g, f, n)-critical covered graphs and present a binding number condition for the existence of fractional (g, f, n)-critical covered graphs, which is an improvement and generalization of a previous result obtained in [2].