AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (2.8 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Decentralized Multigrid for In-situ Big Data Computing

Goutham KamathLei ShiEdmond ChowWenzhan Song( )Junjie Yang
Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA.
College of Computing, Georgia Institute of Technology, Atlanta, GA 30332, USA.
School of Electric and Information Engineering, Shanghai University of Electric Power, Shanghai 200090, China.
Show Author Information

Abstract

Modern seismic sensors are capable of recording high precision vibration data continuously for several months. Seismic raw data consists of information regarding earthquake's origin time, location, wave velocity, etc. Currently, these high volume data are gathered manually from each station for analysis. This process restricts us from obtaining high-resolution images in real-time. A new in-network distributed method is required that can obtain a high-resolution seismic tomography in real time. In this paper, we present a distributed multigrid solution to reconstruct seismic image over large dense networks. The algorithm performs in-network computation on large seismic samples and avoids expensive data collection and centralized computation. Our evaluation using synthetic data shows that the proposed method accelerates the convergence and reduces the number of messages exchanged. The distributed scheme balances the computation load and is also tolerant to severe packet loss.

References

[1]
Song W., Huang R., Xu M., Ma A., Shirazi B., Lahusen R., Air-dropped sensor network for real-time high fidelity volcano monitoring, in The 7th Annual International Conference on Mobile Systems, Applications and Services (MobiSys), 2009.
[2]
Waite G. P., Moranb S. C., VP structure of Mount St. Helens, Washington, USA, imaged with local earthquake tomography, Journal of Volcanology and Geothermal Research, vol. 182, no. 1&2, pp. 113–122, 2009.
[3]
Iyer H. M., Dawson P. B., Imaging Volcanoes Using Teleseismic Tomography. Chapman and Hall, 1993.
[4]
Lees J. M., The Magma system of Mount St. Helens: Non-linear high-resolution P wave tomography, Journal of Volcanology and Geothermal Research, vol. 53, pp. 103–116, 1992.
[5]
Moran S. C., Lees J. M., Malone S. D., P wave crustal velocity structure in the greater Mount Rainier area from local earthquake tomography, Journal of Geophysical Research, vol. 104, no. B5, pp. 10775–10786, 1999.
[6]
Kamath G., Shi L., Song W., Component-average based distributed seismic tomography in sensor networks, in IEEE DCOSS, 2013.
[7]
Lees J. M., Crosson R. S., Bayesian art versus conjugate gradient methods in tomographic seismic imaging: An application at Mount St. Helens, Washington, Institute of Mathematical Statistics, vol. 20, pp. 186–208, 1991.
[8]
Sleeman R., van Eck T., Robust automatic P-phase picking: An on-line implementation in the analysis of broadband seismogram recordings, Physics of the Earth and Planetary Interiors, vol. 113, no. 1–4, pp. 265–275, 1999.
[9]
Tan R., Xing G., Chen J., Song W., Huang R., Quality-driven volcanic earthquake detection using wireless sensor networks, in the 31st IEEE Real-Time Systems Symposium (RTSS), San Diego, CA, USA, 2010.
[10]
Geiger L., Probability method for the determination of earthquake epicenters from the arrival time only, Bull. St. Louis. Univ, vol. 8, pp. 60–71, 1912.
[11]
Heath M. T., Ng E., Peyton B. W., Parallel algorithms for sparse linear systems, SIAM Review, vol. 33, no. 3, pp. 420–460, 1991.
[12]
Bertsekas D. P., Tsitsiklis J. N., Some aspects of parallel and distributed iterative algorithms—A survey, Automatica, vol. 27, no. 1, pp. 3–21, 1991.
[13]
Schizas I. D., Mateos G., Giannakis G. B., Distributed LMS for consensus-based in-network adaptive processing, IEEE Transactions on Signal Processing, vol. 57, no. 6, pp. 2365–2382, 2009.
[14]
Renaut R. A., A parallel multisplitting solution of the least squares problem, Numerical Linear Algebra with Applications, vol. 5, no. 1, pp. 11–31, 1998.
[15]
Kaczmarz S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bulletin International de l'Académie Polonaise des Sciences et des Lettres, vol. 35, pp. 355–357, 1937.
[16]
Herman G. T., Reconstruction from Projections: The Fundamentals of Computerized Tomography. Academic Press, 1980.
[17]
Censor Y., Gordon D., Gordon R., Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Computing, vol. 27, no. 6, pp. 777–808, 2001.
[18]
Censor Y., Gordon D., Gordon R., BICAV: A block-iterative parallel algorithm for sparse systems with pixel-related weighting, IEEE Transaction on Medical Imaging, vol. 20, no. 10, pp. 1050–1060, 2001.
[19]
Gordon D., Gordon R., Component-averaged row projections: A robust, block-parallel scheme for sparse linear systems, SIAM Journal on Scientific Computing, vol. 27, pp. 1092–1117, 2005.
[20]
Elble J. M., Sahinidis N. V., Vouzis P., GPU computing with Kaczmarz's and other iterative algorithms for linear systems, Parallel Computing, vol. 36, pp. 215–231, 2010.
[21]
Trottenberg U., Oosterlee C., Schuller A., Multigrid. Academic Press, 2001.
[22]
Briggs W. L., Henson V. E., McCormick S. F., A multigrid tutorial. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
[23]
Yang U. M., Parallel Algebraic Multigrid Methods—High Performance Preconditioners, vol. 51. Springer-Verlag, 2006, pp. 209–236.
[24]
Chow E., Falgout R. D., Hu J. J., Tuminaro R. S., Yang U. M., A survey of parallelization techniques for multigrid solvers. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2005.
[25]
Smith B., Bjorstad P., Gropp W., Domain Decomposition: Parallel Multi-level Methods for Elliptic Partial Differential Equations. Cambridge University Press, 1996.
[26]
Yserentant H., On the multi-level splitting of finite element spaces, Numer. Math, vol. 49, pp. 379–412, 1986.
[27]
Popa C., Algebraic multigrid smoothing property of Kaczmarz's relaxation for general rectangular linear systems, Electronic Transactions on Numerical Analysis, vol. 29, pp. 150–162, 2008.
[28]
Kostler H., Popa C., Rude U., Algebraic multigrid for general inconsistent linear systems: The correction step, Technical report, Lehrstuhl für Informatik 10 (Systemsimulation), FAU Erlangen-Nürnberg, 2006.
[29]
Popa C., Zdunek R., Kaczmarz extended algorithm for tomographic image reconstruction from limited-data, Mathematics and Computers in Simulation, vol. 65, pp. 579–598, 2004.
[30]
Hansen P. C., Saxild-Hansen M., AIR tools—A MATLAB package of algebraic iterative reconstruction methods, Journal of Computational and Applied Mathematics, vol. 236, no. 8, pp. 2167–2178, 2012.
[31]
Curtis A., Snieder R., Reconditioning inverse problems using the genetic algorithm and revised parameterization, Geophysics, vol. 62, no. 5, pp. 1524–1532, 1997.
Tsinghua Science and Technology
Pages 545-559
Cite this article:
Kamath G, Shi L, Chow E, et al. Decentralized Multigrid for In-situ Big Data Computing. Tsinghua Science and Technology, 2015, 20(6): 545-559. https://doi.org/10.1109/TST.2015.7349927

589

Views

9

Downloads

0

Crossref

N/A

Web of Science

1

Scopus

0

CSCD

Altmetrics

Received: 01 August 2015
Accepted: 19 August 2015
Published: 17 December 2015
© The author(s) 2015
Return