Probabilistic and numerical validation of homology computations for nodal domains
Authors:
Sarah Day, William D. Kalies, Konstantin Mischaikow and Thomas Wanner
Journal:
Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 60-73
MSC (2000):
Primary 60G60, 55-04; Secondary 55N99, 60G15
DOI:
https://doi.org/10.1090/S1079-6762-07-00175-8
Published electronically:
July 11, 2007
MathSciNet review:
2320683
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: Homology has long been accepted as an important computable tool for quantifying complex structures. In many applications these structures arise as nodal domains of real-valued functions and are therefore amenable only to a numerical study, based on suitable discretizations. Such an approach immediately raises the question of how accurate the resulting homology computations are. In this paper we present a probabilistic approach to quantifying the validity of homology computations for nodal domains of random Fourier series in one and two space dimensions, which furnishes explicit probabilistic a-priori bounds for the suitability of certain discretization sizes. In addition, we introduce a numerical method for verifying the homology computation using interval arithmetic.
- Robert J. Adler, The geometry of random fields, John Wiley & Sons, Ltd., Chichester, 1981. Wiley Series in Probability and Mathematical Statistics. MR 611857
- A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Probability and Mathematical Statistics, Academic Press, Inc., Orlando, FL, 1986. MR 856019
- Dirk Blömker, Stanislaus Maier-Paape, and Thomas Wanner, Spinodal decomposition for the Cahn-Hilliard-Cook equation, Comm. Math. Phys. 223 (2001), no. 3, 553–582. MR 1866167, DOI https://doi.org/10.1007/PL00005585
bloemker:etal:p02a D. Blömker, S. Maier-Paape, and T. Wanner. Second phase spinodal decomposition for the Cahn-Hilliard-Cook equation. Transactions of the American Mathematical Society, to appear.
cahn:hilliard:58a J. W. Cahn and J. E. Hilliard. Free energy of a nonuniform system I. Interfacial free energy. Journal of Chemical Physics, 28:258–267, 1958.
carlsson:desilva:03 G. Carlsson and V. de Silva. Topological approximation by small simplicial complexes. Preprint, 2003.
cook:70a H. Cook. Brownian motion in spinodal decomposition. Acta Metallurgica, 18:297–306, 1970.
day:etal:p06a S. Day, W. D. Kalies, and T. Wanner. Homology computations of nodal domains: Accuracy estimates and validation. In preparation, 2007.
desilva:carlsson:04 V. de Silva and G. Carlsson. Topological estimation using witness complexes. In M. Alexa and S. Rusinkiewicz, editors, Eurographics Symposium on Point-Based Graphics. The Eurographics Association, 2004.
- David L. Donoho and Carrie Grimes, Hessian eigenmaps: locally linear embedding techniques for high-dimensional data, Proc. Natl. Acad. Sci. USA 100 (2003), no. 10, 5591–5596. MR 1981019, DOI https://doi.org/10.1073/pnas.1031596100
- J. E. A. Dunnage, The number of real zeros of a random trigonometric polynomial, Proc. London Math. Soc. (3) 16 (1966), 53–84. MR 192532, DOI https://doi.org/10.1112/plms/s3-16.1.53
- Kambiz Farahmand, Topics in random polynomials, Pitman Research Notes in Mathematics Series, vol. 393, Longman, Harlow, 1998. MR 1679392
- Marcio Gameiro, Konstantin Mischaikow, and William Kalies, Topological characterization of spatial-temporal chaos, Phys. Rev. E (3) 70 (2004), no. 3, 035203, 4. MR 2129999, DOI https://doi.org/10.1103/PhysRevE.70.035203
gameiro:etal:05a M. Gameiro, K. Mischaikow, and T. Wanner. Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation. Acta Materialia, 53(3):693–704, 2005.
- Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek, Computational homology, Applied Mathematical Sciences, vol. 157, Springer-Verlag, New York, 2004. MR 2028588
- Jean-Pierre Kahane, Some random series of functions, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 5, Cambridge University Press, Cambridge, 1985. MR 833073
chomp W. Kalies, M. Mrozek, and P. Pilarczyk. Computational homology project. http://www.math.gatech.edu/~chomp/, 2006.
krishan:etal:p05a K. Krishan, M. Gameiro, K. Mischaikow, and M. F. Schatz. Homological characterization of spiral defect chaos in Rayleigh-Benard convection. Preprint, 2005.
- Michael B. Marcus and Gilles Pisier, Random Fourier series with applications to harmonic analysis, Annals of Mathematics Studies, No. 101, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1981. MR 630532
mischaikow:wanner:p06a K. Mischaikow and T. Wanner. Probabilistic validation of homology computations for nodal domains. Annals of Applied Probability 17(3):980-1018, 2007.
niyogi:smale:weinberger:p04a P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete and Computational Geometry, 2007. To appear.
roweis:saul:00 S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, 2000.
- Evelyn Sander and Thomas Wanner, Monte Carlo simulations for spinodal decomposition, J. Statist. Phys. 95 (1999), no. 5-6, 925–948. MR 1712442, DOI https://doi.org/10.1023/A%3A1004550416829
- Evelyn Sander and Thomas Wanner, Unexpectedly linear behavior for the Cahn-Hilliard equation, SIAM J. Appl. Math. 60 (2000), no. 6, 2182–2202. MR 1763320, DOI https://doi.org/10.1137/S0036139999352225
tenenbaum:etal:00 J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000.
- Thomas Wanner, Maximum norms of random sums and transient pattern formation, Trans. Amer. Math. Soc. 356 (2004), no. 6, 2251–2279. MR 2048517, DOI https://doi.org/10.1090/S0002-9947-03-03480-9
adler:81a R. J. Adler. The Geometry of Random Fields. John Wiley & Sons Ltd., Chichester, 1981.
bharuchareid:s:86a A. T. Bharucha-Reid and M. Sambandham. Random Polynomials. Academic Press, Orlando, 1986.
bloemker:etal:01b D. Blömker, S. Maier-Paape, and T. Wanner. Spinodal decomposition for the Cahn-Hilliard-Cook equation. Communications in Mathematical Physics, 223(3):553–582, 2001.
bloemker:etal:p02a D. Blömker, S. Maier-Paape, and T. Wanner. Second phase spinodal decomposition for the Cahn-Hilliard-Cook equation. Transactions of the American Mathematical Society, to appear.
cahn:hilliard:58a J. W. Cahn and J. E. Hilliard. Free energy of a nonuniform system I. Interfacial free energy. Journal of Chemical Physics, 28:258–267, 1958.
carlsson:desilva:03 G. Carlsson and V. de Silva. Topological approximation by small simplicial complexes. Preprint, 2003.
cook:70a H. Cook. Brownian motion in spinodal decomposition. Acta Metallurgica, 18:297–306, 1970.
day:etal:p06a S. Day, W. D. Kalies, and T. Wanner. Homology computations of nodal domains: Accuracy estimates and validation. In preparation, 2007.
desilva:carlsson:04 V. de Silva and G. Carlsson. Topological estimation using witness complexes. In M. Alexa and S. Rusinkiewicz, editors, Eurographics Symposium on Point-Based Graphics. The Eurographics Association, 2004.
donoho:grimes:03 D. L. Donoho and C. Grimes. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Science, 100(10):5591–5596, 2003.
dunnage:66a J. E. A. Dunnage. The number of real zeros of a random trigonometric polynomial. Proceedings of the London Mathematical Society, 16:53–84, 1966.
farahmand:98a K. Farahmand. Topics in Random Polynomials, volume 393 of Pitman Research Notes in Mathematics. Longman, Harlow, 1998.
gameiro:etal:04a M. Gameiro, K. Mischaikow, and W. Kalies. Topological characterization of spatial-temporal chaos. Physical Review E, 70(3):035203, 4, 2004.
gameiro:etal:05a M. Gameiro, K. Mischaikow, and T. Wanner. Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation. Acta Materialia, 53(3):693–704, 2005.
kaczynski:mischaikow:mrozek:04 T. Kaczynski, K. Mischaikow, and M. Mrozek. Computational homology, volume 157 of Applied Mathematical Sciences. Springer-Verlag, New York, 2004.
kahane:85a J.-P. Kahane. Some Random Series of Functions. Cambridge University Press, Cambridge–London–New York, second edition, 1985.
chomp W. Kalies, M. Mrozek, and P. Pilarczyk. Computational homology project. http://www.math.gatech.edu/~chomp/, 2006.
krishan:etal:p05a K. Krishan, M. Gameiro, K. Mischaikow, and M. F. Schatz. Homological characterization of spiral defect chaos in Rayleigh-Benard convection. Preprint, 2005.
marcus:pisier:81a M. B. Marcus and G. Pisier. Random Fourier Series with Applications to Harmonic Analysis, volume 101 of Annals of Mathematics Studies. Princeton University Press, Princeton, 1981.
mischaikow:wanner:p06a K. Mischaikow and T. Wanner. Probabilistic validation of homology computations for nodal domains. Annals of Applied Probability 17(3):980-1018, 2007.
niyogi:smale:weinberger:p04a P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete and Computational Geometry, 2007. To appear.
roweis:saul:00 S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, 2000.
sander:wanner:99a E. Sander and T. Wanner. Monte Carlo simulations for spinodal decomposition. Journal of Statistical Physics, 95(5–6):925–948, 1999.
sander:wanner:00a E. Sander and T. Wanner. Unexpectedly linear behavior for the Cahn-Hilliard equation. SIAM Journal on Applied Mathematics, 60(6):2182–2202, 2000.
tenenbaum:etal:00 J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000.
wanner:04a T. Wanner. Maximum norms of random sums and transient pattern formation. Transactions of the American Mathematical Society, 356(6):2251–2279, 2004.
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (2000):
60G60,
55-04,
55N99,
60G15
Retrieve articles in all journals
with MSC (2000):
60G60,
55-04,
55N99,
60G15
Additional Information
Sarah Day
Affiliation:
College of William and Mary, Department of Mathematics, P.O. Box 8795, Williamsburg, VA 23187
MR Author ID:
646696
Email:
sday@math.wm.edu
William D. Kalies
Affiliation:
Department of Mathematical Sciences, Florida Atlantic University, 777 Glades Road, Boca Raton, FL 33431
Email:
wkalies@fau.edu
Konstantin Mischaikow
Affiliation:
Department of Mathematics, Rutgers University, 110 Frelinghusen Road, Piscataway, NJ 08854
MR Author ID:
249919
Email:
mischaik@math.rutgers.edu
Thomas Wanner
Affiliation:
Department of Mathematical Sciences, George Mason University, 4400 University Drive, MS 3F2, Fairfax, VA 22030
MR Author ID:
262105
Email:
wanner@math.gmu.edu
Keywords:
Homology,
random Fourier series,
nodal domain
Received by editor(s):
November 15, 2006
Published electronically:
July 11, 2007
Additional Notes:
Sarah Day was partially supported by NSF grant DMS-9983660 at Cornell University and NSF grant DMS-0441170 at MSRI
William Kalies was partially supported by NSF grant DMS-0511208 and DOE grant DE-FG02-05ER25713.
Konstantin Mischaikow was partially supported by NSF grants DMS-0511115 and DMS-0107396, by DARPA, and by DOE grant DE-FG02-05ER25711.
Thomas Wanner was partially supported by NSF grant DMS-0406231 and DOE grant DE-FG02-05ER25712.
Communicated by:
Carlos Kenig
Article copyright:
© Copyright 2007
American Mathematical Society