×

zbMATH — the first resource for mathematics

Characterization of discontinuities in high-dimensional stochastic problems on adaptive sparse grids. (English) Zbl 1218.65010
Summary: We present a set of efficient algorithms for detection and identification of discontinuities in high dimensional space. The method is based on extension of polynomial annihilation for discontinuity detection in low dimensions. Compared to the earlier work, the present method poses significant improvements for high dimensional problems. The core of the algorithms relies on adaptive refinement of sparse grids. It is demonstrated that in the commonly encountered cases where a discontinuity resides on a small subset of the dimensions, the present method becomes “optimal”, in the sense that the total number of points required for function evaluations depends linearly on the dimensionality of the space. The details of the algorithms will be presented and various numerical examples are utilized to demonstrate the efficacy of the method.

MSC:
65C30 Numerical solutions to stochastic differential and integral equations
60H15 Stochastic partial differential equations (aspects of stochastic analysis)
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
35R60 PDEs with randomness, stochastic partial differential equations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ghanem, R.; Spanos, P., Stochastic finite elements: A spectral approach, (1991), Springer-Verlag, New York, Inc., New York, NY, USA · Zbl 0722.73080
[2] Xiu, D.; Karniadakis, G., The wiener – askey polynomial chaos for stochastic differential equations, SIAM J. sci. comput., 24, 2, 619-644, (2002) · Zbl 1014.65004
[3] Xiu, D., Fast numerical methods for stochastic computations: a review, Commun. comput. phys., 5, 242-272, (2009) · Zbl 1364.65019
[4] Jakeman, J.; Eldred, M.; Xiu, D., Numerical approach for quantification of epistemic uncertainty, J. comput. phys., 229, 12, 4648-4663, (2010) · Zbl 1204.65008
[5] Gottlieb, D.; Xiu, D., Galerkin method for wave equations with uncertain coefficients, Commun. comput. phys., 3, 2, 505-518, (2008) · Zbl 1195.65009
[6] Le Maitre, O.; Knio, O.; Najm, H.; Ghanem, R., Uncertainty propagation using wiener – haar expansions, J. comput. phys., 197, 1, 28-57, (2004) · Zbl 1052.65114
[7] Ma, X.; Zabaras, N., An adaptive hierarchical sparse grid collocation algorithm for the solution of stochastic differential equations, J. comput. phys., 228, 3084-3113, (2009) · Zbl 1161.65006
[8] Wan, X.; Karniadakis, G., Multi-element generalized polynomial chaos for arbitrary probability measures, SIAM J. sci. comput., 28, 3, 901-928, (2006) · Zbl 1128.65009
[9] Babuska, I.; Tempone, R.; Zouraris, G., Galerkin finite element approximations of stochastic elliptic partial differential equations, SIAM J. numer. anal., 42, 2, 800-825, (2004) · Zbl 1080.65003
[10] Foo, J.; Wan, X.; Karniadakis, G., The multi-element probabilistic collocation method (ME-PCM): error analysis and applications, J. comput. phys., 227, 22, 9572-9595, (2008) · Zbl 1153.65008
[11] Archibald, R.; Gelb, A.; Saxena, R.; Xiu, D., Discontinuity detection in multivariate space for stochastic simulations, J. comput. phys., 228, 7, 2676-2689, (2009) · Zbl 1161.65307
[12] Archibald, R.; Gelb, J.; Yoon, A., Polynomial Fitting for edge detection in irregularly sampled signals and images, SIAM J. numer. anal., 43, 1, 259-279, (2005) · Zbl 1093.41009
[13] Canny, J., A computational approach to edge detection, IEEE trans. pattern anal. machine intell., 8, 679-698, (1986)
[14] Sobel, I., An isotropic 3 image gradient operator, ()
[15] Gardner, T.; Cantor, C.; Collins, J., Construction of a genetic toggle switch in Escherichia coli, Nature, 403, 339-342, (2000)
[16] Xiu, D.; Hesthaven, J., High-order collocation methods for differential equations with random inputs, SIAM J. sci. comput., 27, 3, 1118-1139, (2005) · Zbl 1091.65006
[17] Barthelmann, V.; Novak, E.; Ritter, K., High dimensional polynomial interpolation on sparse grids, Adv. comput. math., 12, 273-288, (2000) · Zbl 0944.41001
[18] Gerstner, T.; Griebel, M., Numerical integration using sparse grids, Numer. algor., 18, 3-4, 209-232, (1998) · Zbl 0921.65022
[19] Gerstner, T.; Griebel, M., Dimension-adaptive tensor-product quadrature, Computing, 71, 1, 65-87, (2003) · Zbl 1030.65015
[20] Babuska, I.; Nobile, F.; Tempone, R., A stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. numer. anal., 45, 3, 1005-1034, (2007) · Zbl 1151.65008
[21] Ganapathysubramanian, B.; Zabaras, N., Modeling diffusion in random heterogeneous media: data-driven models stochastic collocation and the variational multiscale method, J. comput. phys., 226, 1, 326-353, (2007) · Zbl 1124.65007
[22] Nobile, F.; Tempone, R.; Webster, C., An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. numer. anal., 46, 5, 2411-2442, (2008) · Zbl 1176.65007
[23] Xiu, D., Efficient collocation approach for parametric uncertainty analysis, Commun. comput. phys., 2, 2, 293-309, (2007) · Zbl 1164.65302
[24] Zabaras, N.; Ganapathysubramanian, B., A scalable framework for the solution of stochastic inverse problems using a sparse grid collocation approach, J. comput. phys., 227, 9, 4697-4735, (2008) · Zbl 1142.65008
[25] R. Bauer, Band pass filters for determining shock locations, Ph.D. thesis, Applied Mathematics, Brown University, 1995.
[26] Gelb, A.; Tadmor, E., Adaptive edge detectors for piecewise smooth data based on the minmod limiter, J. sci. comput., 28, 2-3, 279-306, (2006) · Zbl 1103.65143
[27] Archibald, R.; Gelb, J.; Yoon, A., Determining the locations of discontinuities in the derivatives of functions, Appl. numer. math., 58, 5, 577-592, (2008) · Zbl 1141.65011
[28] Griebel, M., Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences, Computing, 61, 2, 151-179, (1998) · Zbl 0918.65078
[29] Smolyak, S., Quadrature and interpolation formulas for tensor products of certain classes of functions, Soviet math. dokl., 4, 240-243, (1963) · Zbl 0202.39901
[30] Wang, X.; Sloan, I., Why are high-dimensional finance problems often of low effective dimension, SIAM J. sci. comput., 27, 159-183, (2005) · Zbl 1149.65303
[31] Griebel, M.; Holtz, M., Dimension-wise integration of high-dimensional functions with applications to finance, J. complex., 26, 5, 455-489, (2010) · Zbl 1203.65056
[32] N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press, Cambridge, United Kingdom, 200. · Zbl 0994.68074
[33] Garcke, J.; Griebel, M.; Thess, M., Data mining with sparse grids, Computing, 67, 225-253, (2001) · Zbl 0987.62045
[34] Hegland, M.; Garke, J.; Challis, V., The combination technique and some generalisations, Linear algebra appl., 420, 249-275, (2007) · Zbl 1109.65052
[35] Feuersanger, C.; Griebel, M., Principal manifold learning by sparse grids, Computing, 85, 4, 267-299, (2009) · Zbl 1171.65054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.