چکيده— مساله تجزیه مقادیر تکین (SVD) در تحلیل اطلاعات نقشی مهمی ایفا می نماید و از ارزش کاربردی بسیار زیادی در حوزه های علمی - که با داده های بزرگ سر و کار دارند - برخوردار می باشد. امروزه با توسعه‌ی سریع اینترنت، روند افزایش اطلاعات آنلاین، سریع است. بکارگیری مستقیم محاسبات SVD در ماتریس های بزرگ، زمانبر بوده و نیازمند حافظه زیادی می باشد. برای تسریع محاسبات SVD ، کارهای تحقیقاتی زیادی بر مبنای مدل واسط تبادل پیام (MPI) انجام شده است. با این حال، در پردازش داده های بزرگ، مدل کاهش نگاشت، مزیت‌های بیشتری نسبت به مدل MPI دارد؛ از قبیل تحمل خطا، توازن بار و سادگی. در کاهش نگاشت، روش های موجود فقط بر تخمین رتبه پایین SVD و محاسبه‌ی SVD ماتریس های بلند و باریک (tall and skinny) تمرکز کرده اند و روشی برای محاسبه‌ی SVD با رتبه کامل، ارائه نشده است. در این مقاله ما روشی برای محاسبه SVD با روش تقسیم و غلبه و بر مبنای کاهش نگاشت ارائه می کنیم. به منظور حصول عملکرد بهتر، یک استراتژی زمانبندی دو مرحله ای را طراحی می نماییم که پایه و اساس آن، ویژگی های ریاضی الگوریتم تقسیم و غلبه SVD است. برای افزایش بیشتر کارایی، یک الگوریتم تقسیم بر مبنای روش شاخص – سطر و یک روش پایپ لاین (pipeline) جهت زمانبندی وظیفه ارائه می‌کنیم و در ضرب بلوکی ماتریس ها در چارچوب کاهش نگاشت، تجدید نظر می نماییم. نتایج تجربی، کارایی الگوریتم ما را نشان می‌دهند. روش ما می تواند به شکل موثر، با پروسه محاسبه SVD رتبه کامل برای ماتریس های بزرگ، منطبق شده و مورد استفاده قرار گیرد.
کلمات کليدي-  محاسبات توزیع شده؛ تقسیم و غلبه؛ کاهش نگاشت؛ تجزیه مقدار تکین

Abstract:  Singular Value Decomposition (SVD) shows strong vitality in the area of information analysis, and has significant application value in most of the scientific big data fields. However, with the rapid development of Internet, the information online reveals fast growing trend. For a large-scale matrix, applying SVD computation directly is both time consuming and memory demanding. There are many works available to speed up the computation of SVD based on the Message Passing Interface (MPI) model. However, to deal with large-scale data processing, a MapReduce model has many advantages over a MPI model, such as fault tolerance, load balancing, and simplicity. For a MapReduce environment, existing approaches only focus on low rank SVD approximation and tall-and-skinny matrix SVD computation, and there are no implementations of full rank SVD computation. In this paper, we propose a MapReduce based implementation for solving divide-and-conquer SVD algorithm. To achieve high performance, we design a two-stage task scheduling strategy based on the mathematical characteristics of divide-and-conquer SVD algorithm. To further strengthen the performance, we propose a row-index based divide algorithm, a pipelined task scheduling method, and revised block matrix multiplication in MapReduce framework. Experimental result shows the efficiency of our algorithm. Our implementation can accommodate full rank SVD computation of large-scale matrix very efficiently.
Keywords -Distributed Computation; Divide-and-Conquer; MapReduce; Singular Value Decomposition