Scribd
Upload
67 views24 pages

Numerical Algorithms Overview

This document is a set of lecture notes on parallel algorithm design from Prof. Laxminath Tripathy. It outlines numerical algorithms involving dense matrices, including matrix-vector multiplication, matrix-matrix multiplication, and Gaussian elimination. For each algorithm, it discusses serial complexity and considers parallelizing approaches like 1D and 2D partitioning as well as pipelining. The focus is on analyzing the algorithms and discussing their parallel implementation.

Uploaded by

LaxminathTripathy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
67 views24 pages

Numerical Algorithms Overview

This document is a set of lecture notes on parallel algorithm design from Prof. Laxminath Tripathy. It outlines numerical algorithms involving dense matrices, including matrix-vector multiplication, matrix-matrix multiplication, and Gaussian elimination. For each algorithm, it discusses serial complexity and considers parallelizing approaches like 1D and 2D partitioning as well as pipelining. The focus is on analyzing the algorithms and discussing their parallel implementation.

Uploaded by

LaxminathTripathy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MODULE-4

Notes prepared by
Prof. Laxminath Tripathy
Dept. of Computer Science and Engineering
OEC BBSR.

Referred from text book


Principles of Parallel Algorithm Design
Ananth Grama, Anshul Gupta, George Karypis,
and Vipin Kumar.
Outline
 Focus on numerical algorithms
involving
dense matrices:
􀂅 Matrix-Vector Multiplication
􀂅 Matrix-Matrix Multiplication
􀂅 Gaussian Elimination
 Decompositions & Scalability
Review

Laxminath Tripathy 3
Matrix-Vector Multiplication
• Compute: y = Ax
• y, x are nx1 vectors
• A is an nxn dense matrix
• Serial complexity: W = O(n2).
• We will consider:
• 1D & 2D partitioning.

Laxminath Tripathy 4
Matrix-vector multiplication

Laxminath Tripathy 5
Laxminath Tripathy 6
Laxminath Tripathy 7
Laxminath Tripathy 8
Laxminath Tripathy 9
Laxminath Tripathy 10
Laxminath Tripathy 11
Laxminath Tripathy 12
Laxminath Tripathy 13
Laxminath Tripathy 14
Laxminath Tripathy 15
Laxminath Tripathy 16
• Gaussian Elimination
• Solve Ax=b
A is an nxn dense matrix.
x and b are dense vectors
• Serial complexity:
W = O(n3).
• There are two key steps in each iteration:
Division step
Rank-1 update
• We will consider:
1D & 2D partitioning, and introduce the notion of
pipelining.
Laxminath Tripathy 17
Laxminath Tripathy 18
Laxminath Tripathy 19
Laxminath Tripathy 20
Laxminath Tripathy 21
Laxminath Tripathy 22
Laxminath Tripathy 23
Laxminath Tripathy 24

You might also like