Preconditioning for radial basis functions with domain decomposition methods

In our previous work, an effective preconditioning scheme that is based upon constructing least-squares approximation cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements has shown very attractive numerical results. The preconditioner costs O(N²) flops to set up and O(N) storage. The preconditioning technique is sufficiently general that it can be applied to different types of different operators. This was applied to the 2D multiquadric method, with c~1/√N on the Poisson test problem, the preconditioned GMRES converges in tens of iterations. In this paper, we combine the RBF methods and the ACBF preconditioning technique with the domain decomposition method (DDM). We studied different implementations of the ACBF-DDM scheme and provide numerical results for N > 10,000 nodes. We shall demonstrate that the efficiency of the ACBF-DDM scheme improves dramatically as successively finer partitions of the domain are considered.     

High-Order Methods for Exotic Options and Greeks Under Regime-Switching Jump-Diffusion Models

This paper aims to develop high-order numerical methods for solving the system partial differential equations (PDEs) and partial integro-differential equations (PIDEs) arising in exotic option pricing under regime-switching models and regime-switching jump-diffusion models, respectively. Using cubic Hermite polynomials, the high-order collocation methods are proposed to solve the system PDEs and PIDEs. This collocation scheme has the second-order convergence rates in time and fourth-order rates in space. The computation of the Greeks for the options is also studied. Numerical examples are carried out to verify the high-order convergence and show the efficiency for computing the Greeks.     

Efficient L-stable method for parabolic problems with application to pricing American options under stochastic volatility

Efficient L-stable numerical method for semilinear parabolic problems with nonsmooth initial data is proposed and implemented to solve Heston’s stochastic volatility model based PDE for pricing American options under stochastic volatility. The proposed new method is also used to solve two asset American options pricing problem. Cox and Matthews [S.M. Cox, P.C. Matthews, Exponential time differencing for stiff systems, Journal of Computational Physics 176 (2002) 430-455] developed a class of exponential time differencing Runge-Kutta schemes (ETDRK) for nonlinear parabolic problems. Kassam and Trefethen [A.K. Kassam, L.N. Trefethen, Fourth-order time stepping for stiff PDEs, SIAM Journal on Scientific Computing 26 (4) (2005) 1214-1233] showed that while computing certain functions involved in the Cox-Matthews schemes, severe cancelation errors can occur which affect the accuracy and stability of the schemes. Kassam and Trefethen proposed complex contour integration technique to implement these schemes in a way that avoids these cancelation errors. But this approach creates new difficulties in choosing and evaluating the contour integrals for larger problems. We modify the ETDRK schemes using positivity preserving Padé approximations of the matrix exponential functions and construct computationally efficient parallel version using splitting technique. As a result of this approach it is required only to solve several backward Euler linear problems in serial or parallel.     

Lattice Boltzmann模型在CFD中应用

近年来,格子Boltzmann方法(LBM)已发展为一种模拟流体和物理问题的新颖的、有前景的数值方法,在许多领域的各种数值问题求解上取得很大的成功.文章介绍了一种模拟复杂流动的高效建模数值算法Lattice Boltzmann方法,和它的基本原理及其应用.并通过两个实例数值模拟计算,说明Lattice Boltzmann方法正确、有效,并展示了广阔的应用前景,为今后更深入的研究和广泛应用打下基础.     

Bilevel control of degraded machining system with warm standbys, setup and vacation

In this paper, we study (N, L) switch-over policy for machine repair model with warm standbys and two repairmen. The repairman (R₁) turns on for repair only when N-failed units are accumulated and starts repair after a set up time which is assumed to be exponentially distributed. As soon as the system becomes empty, the repairman (R₁) leaves for a vacation and returns back when he finds the number of failed units in the system greater than or equal to a threshold value N. Second repairman (R₂) turns on when there are L(>N) failed units in the system and goes for a vacation if there are less than L failed units. The life time and repair time of failed units are assumed to be exponentially distributed. The steady state queue size distribution is obtained by using recursive method. Expressions for the average number of failed units in the queue and the average waiting time are established.     

具有Min(N,D,V)-策略控制的M/G/1排队系统

研究服务员具有多重休假和系统采取Min(N,D,V)-策略控制的M/G/1排队系统,运用全概率分解技术和拉普拉斯变换工具,研究了系统队长的瞬态分布和稳态分布,得到了队长瞬态分布的拉普拉斯变换的表达式和稳态队长分布的递推表达式,同时给出了稳态队长的随机分解结果和附加队长分布的显示表达式.进一步讨论了当N→∞,或D→∞,或p{V=∞}=1,或p{V=0}=1的一些特殊情况.最后,在建立系统费用结构模型的基础上,导出了系统长期单位时间的期望费用的显示表达式,并通过数值实例不但确定了使得系统在长期单位时间内的期望费用最小的联合控制策略(N~*,D~*),而且与单一的最优N~*-控制策略和D~*-控制策略进行了比较.     

PDE Models for Pricing Stocks and Options With Memory Feedback

This paper describes partial differential equation (PDE) models for pricing stocks and options in the presence of memory feedback. Of interest are economic situations in which the stock (option) value at time T depends on some type of average of its past values. Derived PDEs resemble viscous Burgers' equations.     

The continuous center set of a network

The continuous radius of a network N is the minimum for all points of N (i.e., vertices or points on edges) of the maximum distance from x to any other point y of N.

Any point of N remote from any other point of a distance not exceeding the continuous radius is a continuous center. The continuous center set of N is the union of all continuous centers.

Properties of the continuous center set are studied and an algorithm is given to determine it, which requires O(m²log m) time and O(m) space in the worst case, m being the number of edges of N.     

On two types of discrete implications

This paper deals with two kinds of implications defined from t-norms, t-conorms and strong negations on a finite chain L: those defined through the expressions I(x, y) = S(N(x), T(x, y)) and I(x, y) = S(T(N(x), N(y)), y). They are called QL-implications and NQL-implications respectively. We mainly study those QL- and NQL-implications derived from smooth t-norms and smooth t-conorms. It is characterized when functions defined in these ways are implication functions, and their analytical expressions are given. It is proved that both kinds of implications agree. Some additional properties are studied like contrapositive symmetry, the exchange principle and others. In particular, it is proved that contrapositive symmetry holds if and only if S is the only Archimedean t-conorm on L, and T jointly with its N-dual t-conorm satisfy the Frank equation. Finally, some QL- and NQL-implications are also derived from non-smooth t-norms or non-smooth t-conorms and many examples are given showing that in this non-smooth case, QL- and NQL-implications remain strongly connected.     

Wiener–Hopf factorization for a group of exponentials of nilpotent matrices

A complete study of the generalized factorization for a group of 2×2 matrix functions of the form G=I+γN, where , I denotes the 2×2 identity matrix and N represents a rational nilpotent matrix function, is presented. A closely related class involving the same matrix N is also studied. The canonical and non-canonical factorizations are considered and explicit formulas are obtained for the partial indices and the factors in such factorizations. It is shown in particular that only one of the columns in the factors needs to be determined, as a solution to a homogeneous linear Riemann–Hilbert problem, the other column being expressed in terms of the first. Necessary and sufficient conditions for existence of a canonical factorization within the same class are established, as well as explicit formulas for the factors in this case.     

Numerical valuation of options under Kou's model

Numerical methods are developed for pricing European and American options under Kou's jump-diffusion model which assumes the price of the underlying asset to behave like a geometrical Brownian motion with a drift and jumps whose size is log-double-exponentially distributed. The price of a European option is given by a partial integro-differential equation (PIDE) while American options lead to a linear complementarity problem (LCP) with the same operator. Spatial differential operators are discretized using finite differences on nonuniform grids and time stepping is performed using the implicit Rannacher scheme. For the evaluation of the integral term easy to implement recursion formulas are derived which have optimal computational cost. When pricing European options the resulting dense linear systems are solved using a stationary iteration. Also for pricing American options similar iterations can be employed. A numerical experiment demonstrates that the described method is very efficient as accurate option prices can be computed in a few milliseconds on a PC. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

两类具有N-策略和单重休假的M/G/1排队系统的最优控制策略

本文考虑两类具有N-策略和服务员单重休假的M/G/1排队系统,其中一类是休假不可中断,另一类是休假可中断。利用系统稳态队长的随机分解特性导出稳态队长的概率母函数,并讨论了系统空闲率与附加平均队长对系统一些参数的敏感性。进一步,在建立费用结构的基础上,应用更新报酬过程理论导出了系统长期运行单位时间内所产生的成本期望费用的显示表达式,同时通过数值计算实例确定了使得系统在长期运行单位时间内所产生的成本期望费用最小的控制策略N^*,以及当休假时间为定长T时的二维最优控制策略（N^*,T^*）。     

Split and balanced colorings of complete graphs

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K_n in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph K_N has a coloring which is not (r, n)-split is denoted by ƒ_r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic K_n in all colors. Then g_r(n) is defined as the smallest N such that K_N has a balanced (r, n)-coloring. The definitions imply that f_r(n) g_r(n). The paper gives estimates and exact values of these functions for various choices of parameters.     

Conservative schemes for the symmetric Regularized Long Wave equations

In this paper, we study the Symmetric Regularized Long Wave (SRLW) equations by finite difference method. We design some numerical schemes which preserve the original conservative properties for the equations. The first scheme is two-level and nonlinear-implicit. Existence of its difference solutions are proved by Brouwer fixed point theorem. It is proved by the discrete energy method that the scheme is uniquely solvable, unconditionally stable and second-order convergent for U in L_∞ norm, and for N in L₂ norm on the basis of the priori estimates. The second scheme is three-level and linear-implicit. Its stability and second-order convergence are proved. Both of the two schemes are conservative so can be used for long time computation. However, they are coupled in computing so need more CPU time. Thus we propose another three-level linear scheme which is not only conservative but also uncoupled in computation, and give the numerical analysis on it. Numerical experiments demonstrate that the schemes are accurate and efficient.     

幂型支付的欧式期权定价公式

在等价鞅测度框架下,讨论了(在到期时刻)期权处于实值状态时支付函数为幂型的股票欧式期权定价公式.这里我们假设无风险利率,股票预期收益率和股价波动率都是时间的确定性函数.本文结果不但包含了原始的Black-Scholes公式,而且可用于上封顶与下保底(幂型)欧式看涨期权的定价.     

Generalized P(N)-graded Lie superalgebras

We generalize the P(N)-graded Lie superalgebras of Martinez-Zelmanov. This generalization is not so restrictive but suffcient enough so that we are able to have a classification for this generalized P(N)-graded Lie superalgebras. Our result is that the generalized P(N)-graded Lie super-algebra L is centrally isogenous to a matrix Lie superalgebra coordinated by an associative superalgebra with a super-involution. Moreover, L is P(N)-graded if and only if the coordinate algebra R is commutative and the super-involution is trivial. This recovers Martinez-Zelmanov's theorem for type P(N). We also obtain a generalization of Kac's coordinatization via Tits-Kantor-Koecher construction. Actually, the motivation of this generalization comes from the Fermionic-Bosonic module construction.     

Optimal space–time adaptive wavelet methods for degenerate parabolic PDEs

We analyze parabolic PDEs with certain type of weakly singular or degenerate time-dependent coefficients and prove existence and uniqueness of weak solutions in an appropriate sense. A localization of the PDEs to a bounded spatial domain is justified. For the numerical solution a space?Ctime wavelet discretization is employed. An optimality result for the iterative solution of the arising systems can be obtained. Finally, applications to fractional Brownian motion models in option pricing are presented.     

Neighborhood unions and cyclability of graphs

A graph G is said to be cyclable if for each orientation of G, there exists a set S of vertices such that reversing all the arcs of with one end in S results in a hamiltonian digraph. Let G be a 3-connected graph of order n36. In this paper, we show that if for any three independent vertices x₁, x₂ and x₃, |N(x₁)N(x₂)|+|N(x₂)N(x₃)|+|N(x₃)N(x₁)|2n+1, then G is cyclable.     

Research Problem

We define an arithmetic invariant for the congruence subgroups Γ₀(N), denoted by

b(Γ₀(N)) and pose the problem of finding good asymptotic upper bonds for b(Γ₀(N)) as N approaches X especially when N is prime or the product of two (not necessarily distinct) primes.