Multiplying Sparse Matrices

Hello everyone,

This week we will be building upon last week's Sparse Matrix lab with the Multiplying Sparse Matrices lab. As the name implies, this week's lab will be about multiplying two sparse matrices. As always feel free to leave a comment that is related to this week's lab and lets get right into this lab.

The Lab

Continuing on from the Sparse Matrices lab, we create two new classes that inherit from Matrix and SparseMatrix called MatrixWithMult and SparseMatrixWithMult. In each of these classes, we define a multiple() method that takes in two matrices. In MatrixWithMult::multiply(), we implement the slow, naive solutions, while in SparseMatrixWithMult::multiply(), we implement a more optimized solution.

The Implementation

In SparseMatrixWithMult::multiply(), we need to implement a solution that takes advantage of what we know about matrix multiplication and the sparse matrices themselves. Starting off with the sparse matrices themselves, we need to avoid utilizing SparseMatrix::get() because it takes time to traverse the given SparseMatrix and return something. Since our SparseMatrix class stores the data internally using an array of linked lists, we can just retrieve the list from a given row and traverse it instead of using get().

However, traversing a list is not enough to quickly multiply sparse matrices. This is where we start exploiting what we know about matrix multiplication. Matrix multiplication is essentially the dot product of a given row in one matrix and a given column in the other matrix. Dot product is founded by summing the products of the corresponding terms, meaning if one of the terms is 0, the product will be 0. With this in mind, we can use this to make our algorithm faster by skipping rows of empty values and skipping multiplication operations that we know will result in 0.

A summary of the optimizations are as followed:

• Traverse the linked-lists in a designated row instead of using the get() method.
• Skip rows that are entirely empty (which means the value is 0)
• Skip multiplication if the value in a given column is 0.

Lab Questions

Q: Compare your Matrix's multiply() and SparseMatrix's multiply() methods. Is there a relation between the number of elements and the time taken to multiply()?

A: If we multiply two matrices of 500 x 500, the Matrix's multiply() will take longer since it will process each element in the two matrices. SparseMatrix's multiply(), however, will be faster since it will ignore elements that are considered to be default values (or 0 in some cases).

Q: What is the effect of the EDD (effective data density) on the time taken to multiply two sparse matrices? What about the non-sparse matrices?

A: As the number of non-default values becomes closer to the total number of values, the time it takes to multiply two sparse matrices would probably end up taking the same amount of time it takes to multiply a non-sparse matrix, since the more non-default values we have in a sparse matrix, the closer SparseMatrixWithMult::multiply() will behave as Matrix::multiply()

Q: Does it make sense to keep the lists sorted by column number?

A: It is not practical to keep the lists sorted by column number if your are iterating through them within multiply() since dot product is the sum of the products of the corresponding terms, meaning you can multiply the pair of terms in any order. 

Q: Does it matter if the lists have duplicate cells (i.e. same column number)?

A: I would not say that having duplicate cells will do much in the sense of multiplying sparse matrices. It would still undergo the same process as if it was not a duplicate cell, so nothing special would happen.

Q: There is significant scope for further optimization. Discuss such ideas.

A: Besides the ones that I have just mentioned, there was one algorithm I read about (the Strassen algorithm) that would split up the matrix into smaller parts and do the multiplication operations on them.

Conclusion

Overall, the multiplying sparse matrices lab is all about limiting the number of times we need to access a sparse matrix and exploiting the rules of matrix multiplication. There are some algorithms out there that provide faster matrix multiplication than the one I was explaining here, but utilizes advance ideas out of my scope. Thank you for reading and feel free to leave a comment.

Sparse Matrices

Hello everyone,

This week I am bringing you another discussion of a recent lab I was doing for CS class. This week I will be discussing about Sparse Matrices. As always, feel free to leave a comment on any questions you may have and and conceptual mistakes I may have made while writing this post.

What is a Sparse Matrix?

A sparse matrix is essentially a matrix with most of its elements being zero. An example would be that I have a 500 by 500 matrix to store integer values, but I only use about 100 spots out of the possible 250000. A sparse matrix in a computer program is looked down upon because we are wasting a lot of memory on a few values. There are some ways to lower the amount of memory used on sparse matrices, with one involving the use of arrays and linked lists.

An Ideal Implementation for Matrices

Since the lab I was doing was for a C++ course, I will be referring to the vector data type in the C++ Standard Template Library (STL). I will also be referring to the list data type in C++ STL as it is a linked list implementation.

Starting off, a typical matrix would be stored in a two-dimensional array. What is beneficial about this implementation is that it allows for quick, random access to elements within the matrix. The downside is that if the matrix is sparse, we are wasting memory.

In the implementation I will be discussing about, we will be utilizing an array and a linked list. The array will be initialized to be an array of linked lists, meaning each element within the array represents a row in the matrix. The linked lists will represent the columns, whose nodes will contain the column number and the data value being stored.

The idea behind this implementation is that we are only spending memory on a one-dimensional array. From there, our linked list will contain nodes for data values that are nonzero (or if you are doing a template approach, not a default value). If the linked list for a given row does not contain a node with a given column number, it is the equivalent of saying there is a zero at the given (row, column) coordinates.

The downside of this implementation is that access speed to elements is a bit slow, because even if we are given coordinates, we need to traverse the linked list at a given row searching for the given column value. But this implementation does save memory in the end.

Questions Given in the Lab

Just like the last post, this lab includes a few questions regarding to the kinds of things we can do in software to save memory:
Q: What is the trade-off of using software to give save resources instead of using better hardware?
A: If we utilize algorithms and software to save on the amount of resources used computers, I would say that we will be trading off speed for resource efficiency. I believe this is being done with zip files, where the software needs time to compress and package given files and uncompressed them when unzipped.

Q: vector::at() returns a reference that you can use as both an rvalue (RHS of assignment) as well as an lvalue. Is it possible to implement such an accessor for SparseMatrices (the class I was implementing)?
A: I would say it is possible to implement such an accessor for SparseMatrices. If vector::at() is returning the reference of an object and it is being called on the right-hand side of an assignment, then we are just assigning that object to another one. If we want our SparseMatrices accessor be used on the left-hand side of an assignment, the objects SparseMatrices contains need to have an overloaded assignment operator.

Q: In C++ two different functions cannot differ in their return types only. Discuss why you think this restriction exists in the language standard.
A: I believe this restriction exists in the language standard because of ambiguity. If we have two functions with the same name, amount of parameters, but different return type, how can it tell which return type to use.

Q: Does it make sense to keep your lists sorted?
A: If the nodes within a linked list were sorted such that columns on the left-most side appear first, then it would provide faster access time in the ideal case, since it will not have to search to far for a certain column number. However, in the worst case it may still require a traversal through the entire list.

Conclusion

This lab is a pretty interesting lab since we get to see how we can use simple techniques to effectively save on that sweet precious memory. Although there are probably more methods of implementing an efficient matrix, the implementation is considered to be a pretty simple one. I hope you enjoy this post. As mentioned before, feel free to leave a comment on anything relevant to the material presented here, questions, and mistakes that I have made when writing this post so I can fix them.

Thank you so much for reading!

The Subset Sum Problem

Hello visitors,

This blog was started as a way to discuss some interesting things about programmings done in my CS class. Meaning that I will probably make mistakes in my discussion, so consider this as an early warning. Nevertheless, we will start this blog off with the Subset Sum Problem.

After spending some time reading about Subset Sum, this problem is seem to be a common dynamic programming problem. However for my class, we will be tackling it using mainly logic and other optimizations.

Our Task

Given a list of numbers (which we will call the "master list"), we are tasked to find a subset whose sum is as large as possible, but not larger than a given target value.

Brute-Force Solution

The brute-force solution would simply be to create the power set of the given list of numbers and then go through each subset in the power set until we find the best possible subset. However, this would be pretty slow since we first have to make all the possible subsets (which is equal to 2^N, where N is the number of terms in the list), some of which may have a sum greater than the target.

Optimizing our Brute-Force Solution

The Subset Sum Problem already is inherently slow, but there are a few simple things we can do to optimize the brute force solution to achieve slightly better performance:

1. Use loops to create the power set instead of recursion
2. When creating the subsets, prune out subsets whose sums are bigger than the target value (since adding more terms to them will result in a bigger sum) and check for subsets whose sum is actually equal to the target value (since that is essentially the best solution available).
3. Skip individual items in the master list whose value is greater than the target value (same as the region mentioned in point 2).
4. Check to see if the master list is empty (because an empty set would then be the solution)
5. Check if the sum of all the elements in the master list is less than the target (if it is, then the master list itself is the solution and we are done). 

Interesting Optimization Questions

I already mentioned that even with the kinds of optimizations above, the algorithm in the worst-case would still be slow. Along with the lab, we were given three questions pertaining to what other factors affect the performance of the algorithm:

1. Does a particular order of processing the master set elements work better than others (e.g. Does sorting the list of items help?)
• Typically sorting the list would not necessarily do much for performance.  Depending on how the list is sorted, it can knock out viable sets earlier in the creation process, but will still take around the same amount of time for an unsorted list.
2. Does the value of the target matter (i.e. are certain targets likely to be reached faster?)
• Low target values would generally cause the search for the best subset to be faster, since it does not require subsets with really big sums. High target values causes the search to become longer because it requires subsets with big sums.
3. Does the nature of the probability distribution from which the master set elements are drawn matter? (e.g. Can the algorithm take advantage of the fact if you knew that the
   master set elements were drawn from a particular probability distribution (e.g. a
   Gaussian, uniform or exponential distribution, etc.)
• If the algorithm knows what kinds of values would appear most often, then it could use them to make different combinations of subsets until it finds the best solution. Though, it might still take some significant amount of time when doing so. 

Conclusion

Overall, the Subset Sum Problem is inherently slow. The optimizations mentioned would provide a modest performance boost, but not a significant one.  Going through the optimization questions, the value of the target will be what causes the algorithm to take more or less time in searching for the best subset. And yeah, this is my take on the Subset Sum problem. I hope this was an interesting read, and please leave comments down below on related topics and/or mistakes that need correction.

Thank you for reading and have a good day!