When solving the American options with or without dividends, numerical methods often obtain lower convergence rates if further treatment is not implemented even using high-order schemes. In this article, we present a fast and explicit fourth-order compact scheme for solving the free boundary options. In particular, the early exercise features with the asset option and option sensitivity are computed based on a coupled of nonlinear PDEs with fixed boundaries for which a high order analytical approximation is obtained. Furthermore, we implement a new treatment at the left boundary by introducing a third-order Robin boundary condition. Rather than computing the optimal exercise boundary from the analytical approximation, we simply obtain it from the asset option based on the linear relationship at the left boundary. As such, a high order convergence rate can be achieved. We validate by examples that the improvement at the left boundary yields a fourth-order convergence rate without further implementation of mesh refinement, Rannacher time-stepping, and/or smoothing of the initial condition. Furthermore, we extensively compare, the performance of our present method with several 5(4) Runge-Kutta pairs and observe that Dormand and Prince and Bogacki and Shampine 5(4) pairs are faster and provide more accurate numerical solutions. Based on numerical results and comparison with other existing methods, we can validate that the present method is very fast and provides more accurate solutions with very coarse grids.
相關內容
In 1961, Gomory and Hu showed that the max-flow values of all $n\choose 2$ pairs of vertices in an undirected graph can be computed using only $n-1$ calls to any max-flow algorithm. Even assuming a linear-time max-flow algorithm, this yields a running time of $O(n^3)$ for this problem. We break this 60-year old barrier by giving an $\tilde{O}(n^{23/8})$-time algorithm for the Gomory-Hu tree problem. Our result is unconditional, i.e., it does not rely on a linear-time max-flow algorithm.
We propose and analyze a pressure-stabilized projection Lagrange--Galerkin scheme for the transient Oseen problem. The proposed scheme inherits the following advantages from the projection Lagrange--Galerkin scheme. The first advantage is computational efficiency. The scheme decouples the computation of each component of the velocity and pressure. The other advantage is essential unconditional stability. Here we also use the equal-order approximation for the velocity and pressure, and add a symmetric pressure stabilization term. This enriched pressure space enables us to obtain accurate solutions for small viscosity. First, we show an error estimate for the velocity for small viscosity. Then we show convergence results for the pressure. Numerical examples of a test problem show higher accuracy of the proposed scheme for small viscosity.
This paper is concerned with superconvergence properties of the direct discontinuous Galerkin (DDG) method for two-dimensional nonlinear convection-diffusion equations. By using the idea of correction function, we prove that, for any piecewise tensor-product polynomials of degree $k\geq 2$, the DDG solution is superconvergent at nodes and Lobatto points, with an order of ${\cal O}(h^{2k})$ and ${\cal O}(h^{k+2})$, respectively. Moreover, superconvergence properties for the derivative approximation are also studied and the superconvergence points are identified at Gauss points, with an order of ${\cal O}(h^{k+1})$. Numerical experiments are presented to confirm the sharpness of all the theoretical findings.
In this paper, we revisit the $L_2$-norm error estimate for $C^0$-interior penalty analysis of Dirichlet boundary control problem governed by biharmonic operator. In this work, we have relaxed the interior angle condition of the domain from $120$ degrees to $180$ degrees, therefore this analysis can be carried out for any convex domain. The theoretical findings are illustrated by numerical experiments. Moreover, we propose a new analysis to derive the error estimates for the biharmonic equation with Cahn-Hilliard type boundary condition under minimal regularity assumption.
We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an $n$-point set $X \subset \{1,2,\dots,\Delta\}^d$, and computing the Earth Mover Distance (EMD) between two multi-sets $A,B \subset \{1,2,\dots,\Delta\}^d$ of size $n$. We consider the turnstile model, where points can be added and removed. We give a one-pass streaming algorithm for MST and a two-pass streaming algorithm for EMD, both achieving an approximation factor of $\tilde{O}(\log n)$ and using polylog$(n,d,\Delta)$-space only. Furthermore, our algorithm for EMD can be compressed to a single pass with a small additive error. Previously, the best known sublinear-space streaming algorithms for either problem achieved an approximation of $O(\min\{ \log n , \log (\Delta d)\} \log n)$ [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20]. For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of $\Omega(\log n)$, analogous to the $\Omega(\log n)$ lower bound for EMD of [Andoni-Indyk-Krauthgamer '08]. Our algorithms are based on an improved analysis of a recursive space partitioning method known generically as the Quadtree. Specifically, we show that the Quadtree achieves an $\tilde{O}(\log n)$ approximation for both EMD and MST, improving on the $O(\min\{ \log n , \log (\Delta d)\} \log n)$ approximation of [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20].
Flakiness is a major concern in Software testing. Flaky tests pass and fail for the same version of a program and mislead developers who spend time and resources investigating test failures only to discover that they are false alerts. In practice, the defacto approach to address this concern is to rerun failing tests hoping that they would pass and manifest as false alerts. Nonetheless, completely filtering out false alerts may require a disproportionate number of reruns, and thus incurs important costs both computation and time-wise. As an alternative to reruns, we propose Fair, a novel, lightweight approach that classifies test failures into false alerts and legitimate failures. Fair relies on a classifier and a set of features from the failures and test artefacts. To build and evaluate our machine learning classifier, we use the continuous integration of the Chromium project. In particular, we collect the properties and artefacts of more than 1 million test failures from 2,000 builds. Our results show that Fair can accurately distinguish legitimate failures from false alerts, with an MCC up to 95%. Moreover, by studying different test categories: GUI, integration and unit tests, we show that Fair classifies failures accurately even when the number of failures is limited. Finally, we compare the costs of our approach to reruns and show that Fair could save up to 20 minutes of computation time per build.
We investigate identifying the boundary of a domain from sample points in the domain. We introduce new estimators for the normal vector to the boundary, distance of a point to the boundary, and a test for whether a point lies within a boundary strip. The estimators can be efficiently computed and are more accurate than the ones present in the literature. We provide rigorous error estimates for the estimators. Furthermore we use the detected boundary points to solve boundary-value problems for PDE on point clouds. We prove error estimates for the Laplace and eikonal equations on point clouds. Finally we provide a range of numerical experiments illustrating the performance of our boundary estimators, applications to PDE on point clouds, and tests on image data sets.
An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters [n,k,d] and the list size L. L-MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed-Solomon (GRS) codes.
We show that the mass matrix derived from finite elements can be effectively used as a preconditioner for iteratively solving the linear system arising from finite-difference discretization of the Poisson equation, using the conjugate gradient method. We derive analytically the condition number of the preconditioned operator. Theoretical analysis shows that the ratio of the condition number of the Laplacian to the preconditioned operator is $8/3$ in one dimension, $9/2$ in two dimensions, and $2^9/3^4 \approx 6.3$ in three dimensions. From this it follows that the expected iteration count for achieving a fixed reduction of the norm of the residual is smaller than a half of the number of the iterations of unpreconditioned CG in 2D and 3D. The scheme is easy to implement, and numerical experiments show its efficiency.
Importance sampling is one of the most widely used variance reduction strategies in Monte Carlo rendering. In this paper, we propose a novel importance sampling technique that uses a neural network to learn how to sample from a desired density represented by a set of samples. Our approach considers an existing Monte Carlo rendering algorithm as a black box. During a scene-dependent training phase, we learn to generate samples with a desired density in the primary sample space of the rendering algorithm using maximum likelihood estimation. We leverage a recent neural network architecture that was designed to represent real-valued non-volume preserving ('Real NVP') transformations in high dimensional spaces. We use Real NVP to non-linearly warp primary sample space and obtain desired densities. In addition, Real NVP efficiently computes the determinant of the Jacobian of the warp, which is required to implement the change of integration variables implied by the warp. A main advantage of our approach is that it is agnostic of underlying light transport effects, and can be combined with many existing rendering techniques by treating them as a black box. We show that our approach leads to effective variance reduction in several practical scenarios.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191