Parallelism in Matrix Computations

این کتاب اساساً به عنوان یک تک نگاری تحقیقاتی در نظر گرفته شده است که می تواند در دوره های تحصیلات تکمیلی برای طراحی الگوریتم های موازی در محاسبات ماتریسی نیز استفاده شود.

این کتاب دانش کلی اما نه گسترده ای از خطی عددی را فرض می کند. جبر، معماری های موازی، و پارادایم های برنامه نویسی موازی.

این کتاب شامل چهار بخش است: (I) مبانی. (II) محاسبات ماتریسی متراکم و ویژه. (III) محاسبات ماتریس پراکنده. و (IV) توابع و ویژگی های ماتریس. بخش اول به پارادایم‌های برنامه‌نویسی موازی و هسته‌های بنیادی، از جمله طرح‌های مرتب‌سازی مجدد برای ماتریس‌های پراکنده می‌پردازد. بخش دوم به محاسبات ماتریسی متراکم مانند الگوریتم‌های موازی برای حل سیستم‌های خطی، حداقل مربعات خطی، مسئله مقادیر ویژه جبری متقارن، و تجزیه ارزش تکی اختصاص دارد. همچنین با توسعه الگوریتم‌های موازی برای سیستم‌های خطی خاص مانند سیستم‌های نواری، واندرموند، تاپلیتز و بلوک تاپلیتز سروکار دارد. بخش سوم به محاسبات ماتریس پراکنده می‌پردازد: (الف) توسعه حل‌کننده‌های سیستم خطی تکراری موازی با تأکید بر پیش‌شرطی‌کننده‌های مقیاس‌پذیر، (ب) طرح‌های موازی برای به دست آوردن چند جفت ویژه شدید یا آن‌هایی که در یک بازه معین در طیف یک استاندارد وجود دارند. یا مسئله ارزش ویژه متقارن تعمیم یافته، و (ج) روش های موازی برای محاسبه چند تا از سه گانه های مفرد شدید. بخش چهارم بر توسعه الگوریتم های موازی برای توابع ماتریس و ویژگی های خاص مانند شبه طیف ماتریس و تعیین کننده تمرکز دارد. این کتاب همچنین پیشینه نظری و عملی لازم هنگام طراحی این الگوریتم‌ها را مرور می‌کند و شامل کتاب‌شناسی گسترده‌ای است که برای محققان و دانشجویان مفید خواهد بود.

این کتاب بسیاری از الگوریتم‌های موجود را گرد هم می‌آورد. برای محاسبات ماتریس بنیادی که دارای سابقه اثبات شده اجرای کارآمد از نظر مکان داده و انتقال داده بر روی سیستم های پیشرفته، و همچنین چندین الگوریتم که برای اولین بار ارائه می شوند، با تمرکز بر فرصت های موازی و استحکام الگوریتم.

This book is primarily intended as a research monograph that could also be used in graduate courses for the design of parallel algorithms in matrix computations.

It assumes general but not extensive knowledge of numerical linear algebra, parallel architectures, and parallel programming paradigms.

The book consists of four parts: (I) Basics; (II) Dense and Special Matrix Computations; (III) Sparse Matrix Computations; and (IV) Matrix functions and characteristics. Part I deals with parallel programming paradigms and fundamental kernels, including reordering schemes for sparse matrices. Part II is devoted to dense matrix computations such as parallel algorithms for solving linear systems, linear least squares, the symmetric algebraic eigenvalue problem, and the singular-value decomposition. It also deals with the development of parallel algorithms for special linear systems such as banded ,Vandermonde ,Toeplitz ,and block Toeplitz systems. Part III addresses sparse matrix computations: (a) the development of parallel iterative linear system solvers with emphasis on scalable preconditioners, (b) parallel schemes for obtaining a few of the extreme eigenpairs or those contained in a given interval in the spectrum of a standard or generalized symmetric eigenvalue problem, and (c) parallel methods for computing a few of the extreme singular triplets. Part IV focuses on the development of parallel algorithms for matrix functions and special characteristics such as the matrix pseudospectrum and the determinant. The book also reviews the theoretical and practical background necessary when designing these algorithms and includes an extensive bibliography that will be useful to researchers and students alike.

The book brings together many existing algorithms for the fundamental matrix computations that have a proven track record of efficient implementation in terms of data locality and data transfer on state-of-the-art systems, as well as several algorithms that are presented for the first time, focusing on the opportunities for parallelism and algorithm robustness.