Matrix Multiplication Methods and Algorithms

Slide Note

The process of matrix multiplication is explored through different methods such as Direct Method, Divide and Conquer, and Strassen's Method. Each method offers insights into optimizing the number of multiplications required for multiplying matrices of various sizes. Advantages and disadvantages of divide and conquer algorithms are discussed, along with the analysis of recurrence relations and the benefits of parallelism. Various algorithms like Binary Search, Mergesort, Quicksort, and Strassen algorithm are outlined, presenting a comprehensive overview of matrix multiplication techniques.

drey_ona Follow

Uploaded on Apr 30, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Matrix Multiplication DirectMethod: Suppose we want to multiply twon x n matrices, A andB. Their product, C=AB, will be an n by n matrix and will therefore have n2elements. The number of multiplications involved in producing the product in this way is (n3) 1

MatrixMultiplication Divide and Conquer method for Matrixmultiplication How manyMultiplications? 8multiplications for matricesof sizen/2 xn/2 and 4 additions. Addition of two matrices takes O(n2) time. So the time complexity can be written as T(n) = 8T(n/2) + O(n2) which happen to be O(n3); same as the directmethod 2

Stressens matrixmultiplication Multiplicationof 2 2 matrices: By using divide-and-conquer approach we can reduce the number of multiplications. Such an algorithm was published by V . Strassen in1969. 3

Strassens matrixmultiplication The principal insight of thealgorithm product C of two 2 2 matrices A andB with just sevenmultiplications This is accomplished by 4

Strassens matrix multiplication 5

Analysis Recurrence relation (considering only multiplication) 7

Analysis ( From T2: Horowitz et al) 8

Advantages and Disadvantages of Divide& Conquer Parallelism: Divide and conquer algorithms tend to havea lot of inherentparallelism. CachePerformance: Once a sub-problem fits in the cache, the standard recursive solution reuses the cached datauntil the sub-problem has been completelysolved. It allows solving difficult and often impossible looking problems like the Tower ofHanoi X Recursion isslow sometimes it can become more complicated than a basic iterative approach, the same sub problem can occur many times. It is solvedagain. 9

Module 2 Outline Divide andConquer 1. 2. 3. Algorithm: Binarysearch 4. Algorithm: Finding the maximum and minimum 5. Algorithm: Mergesort 6. Algorithm: Quicksort 7. Algorithm: Strassen s matrixmultiplication 8. Advantages andDisadvantages 9. Decrease and ConquerApproach 10. Algorithm: TopologicalSort Generalmethod Recurrenceequation 10

Decrease and ConquerApproach There are three major variations ofdecrease- and- conquer: decrease-by-a-constant, most often by one (e.g., insertion sort) decrease-by-a-constant-factor, most often by the factor of two (e.g., binarysearch) variable-size-decrease (e.g., Euclid salgorithm) 11

TopologocalSorting Graph,Digraph Adjacency matrix and adjacency list DFS,BFS 12

Tree Edge: It is an edge which is present in the tree obtained after applying DFS on the graph ab,bc,de. Forward Edge: It is an edge (u, v) such that v is descendant but not part of the DFS tree. ac Back edge: It is an edge (u, v) such that v is ancestor of node u but not part of DFS tree. ba . Presence of back edge indicates a cycle in directed graph. Cross Edge: It is a edge which connects two node such that they do not have any ancestor and a descendant relationship between them. dc

Digraph A directed cycle in a digraph is a sequence of three or more of its vertices that starts andends with the samevertex For example, a, b, a is a directed cycle in the digraph in Figuregivenabove. Conversely, if a DFS forest of a digraph has no back edges, the digraph is a dag, an acronym for directed acyclicgraph. 18

Motivation for topologicalsorting Consider a set of five required courses {C1, C2, C3, C4, C5} a part-time student has to take in some degree program. The courses can be taken in any order as long as the following course prerequisites aremet: C1 and C2 have no prerequisites, C3 requires C1 and C2, C4 requires C3,and C5 requires C3 and C4. The student can take only one course perterm. Inwhichorder shouldthe studenttakethe courses? 19

TopologicalSort For topological sorting to be possible, a digraph in question must be aDAG. There are two efficient algorithms that both verify whether a digraph is a dag and, if it is, produce an ordering of vertices that solves the topological sorting problem. The first one is based on depth-firstsearch the second is based on a direct application of the decrease-by-onetechnique. 20

Topological Sorting based onDFS Method 1. Perform a DFS traversal and note the order in which vertices becomedead-ends 2. Reversing this order yields a solution to the topological sortingproblem, provided, no back edge has been encountered during the traversal. If a back edge has been encountered, the digraph is not a dag, and topological sorting of itsvertices is impossible. 21

TopologicalSortingusing decrease-and-conquer technique: Method: The algorithm is based on a direct implementation of the decrease-(by one)-and-conquer technique: 1. Repeatedly, identify in a remaining digraph a source, which is a vertex withno incoming edges, and delete it along withall the edges outgoing from it. (If there areseveralsources,breakthe tie arbitrarily.If there are none, stop because the problem cannot be solved.) 2. Theorderin whichtheverticesaredeletedyields a solution to thetopological sorting problem. 23

Illustration 24

Applications of TopologicalSorting Observation: Topological sorting problem may have several alternativesolutions. Instruction scheduling in programcompilation Cell evaluation ordering in spreadsheetformulas, Resolving symbol dependencies inlinkers. 25

Summary Divide andConquer Recurrenceequation Binarysearch Finding the maximum andminimum Mergesort Quicksort Strassen s matrixmultiplication Advantages and Disadvantages of D & C Decrease and ConquerApproach Algorithm: TopologicalSort 26