Distributed QR Factorization Based on Randomized Algorithms

详细信息    查看全文

• 作者：Hana Straková (1) Hana.Strakova@univie.ac.at
  Wilfried N. Gansterer (1) Wilfried.Gansterer@univie.ac.at
  Thomas Zemen (2) Thomas.Zemen@ftw.at
• 关键词：distributed vs. parallel QR factorization – decentralized QR factorization – evaluation of distributed algorithms – gossip algorithms – push ; sum algorithm – randomized communication schedule – fault ; tolerance
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7203
• 期：1
• 页码：235-244
• 全文大小：273.4 KB
• 参考文献：1. Abdelhak, S., Chaudhuri, R.S., Gurram, C.S., Ghosh, S., Bayoumi, M.: Energy-aware distributed QR decomposition on wireless sensor nodes. The Computer Journal 54(3), 373–391 (2011)
  2. Aysal, T., Yildiz, M., Sarwate, A., Scaglione, A.: Broadcast gossip algorithms for consensus. IEEE Trans. Signal Processing 57(7), 2748–2761 (2009)
  3. Blackford, L., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.C.: ScaLAPACK Users’ Guide. SIAM, Philadelphia (1997)
  4. Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Trans. Information Theory 52(6), 2508–2530 (2006)
  5. Buttari, A., Langou, J., Kurzak, J., Dongarra, J.: Parallel Tiled QR Factorization for Multicore Architectures. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) PPAM 2007. LNCS, vol. 4967, pp. 639–648. Springer, Heidelberg (2008)
  6. Demmel, J., Grigori, L., Hoemmen, M.F., Langou, J.: Communication-optimal parallel and sequential QR and LU factorizations. Tech. rep. no. UCB/EECS-2008-89, EECS Department, University of California, Berkeley (2008)
  7. Dimakis, A., Kar, S., Moura, J., Rabbat, M., Scaglione, A.: Gossip algorithms for distributed signal processing. Proceedings of the IEEE 98(11), 1847–1864 (2010)
  8. Dumard, C., Riegler, E.: Distributed sphere decoding. In: International Conference on Telecommunications, ICT 2009, pp. 172–177 (2009)
  9. Gansterer, W.N., Niederbrucker, G., Strakova, H., Schulze Grotthoff, S.: Scalable and fault tolerant orthogonalization based on randomized aggregation. To Appear in Journal of Computational Science
  10. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press (1996)
  11. Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: FOCS 2003: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 482–491. IEEE Computer Society (2003)
  12. Kempe, D., McSherry, F.: A decentralized algorithm for spectral analysis. Journal of Computer and System Sciences 74(1), 70–83 (2008)
  13. Kielbasinski, A., Schwetlick, H.: Numeryczna algebra liniowa, 2nd edn. Wydawnictwo Naukowo-Techniczne, Warszawa (1994) (in Polish)
  14. Ozgur, A., Leveque, O., Tse, D.: Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks. IEEE Transactions on Information Theory 53(10), 3549–3572 (2007)
  15. Rabbat, M., Nowak, R.: Distributed optimization in sensor networks. In: Third International Symposium on Information Processing in Sensor Networks, pp. 20–27 (2004)
  16. Song, F., Ltaief, H., Hadri, B., Dongarra, J.: Scalable tile communication-avoiding QR factorization on multicore cluster systems. In: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–11 (2010)
  17. Yu, Y., Krishnamachari, B., Prasanna, V.: Energy-latency tradeoffs for data gathering in wireless sensor networks. In: INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1 (2004)
• 作者单位：1. Research Group Theory and Applications of Algorithms, University of Vienna, Austria2. Forschungszentrum Telekommunication Wien, Austria
• ISSN：1611-3349

文摘

Most parallel algorithms for matrix computations assume a static network with reliable communication and thus use fixed communication schedules. However, in situations where computer systems may change dynamically, in particular, when they have unreliable components, algorithms with randomized communication schedule may be an interesting alternative.