Linear Algebra Algorithms Exam

 Linear Algebra Algorithms Exam

General Instructions 1. Submission of a solution to this exam constitutes a statement that you followed these instructions.

If you failed to follow some of the instructions for whatever reason, explain at the top of the exams which instructions you failed to follow, how you solved the relevant parts of the exam, and why.

2. The exam is individual. You may not discuss the exam, your solutions or other solutions, or anything having to do with the algorithms and computations that the exam focuses on with any person except Sivan Toledo. You must follow this rule before, during, and after you solve the exam (including in the periods before you start the exam and after you submit your solution, since different students may solve it at different times).

3. You may only discuss this exam with persons other than Sivan Toledo after the grades are published.

Linear Algebra Algorithms Exam

4. You may use any publicly-accessible non-human resource to solve the exam, but you must cite every resource that you use. For books, articles, web sites, and so on, cite the title, author, and URL, and explain how you used the resource. For AI tools and other responsive resources, give the name of the tool (and URL if not well known) and the prompts. If the interaction was complex, just summarize the interaction. In both cases, explain how you used the results.

5. Include all the code that you used, and mark clearly code that you wrote, code from other sources (static or responsive/AI). If you fixed or corrected existing or generated code, indicate your changes or fixes clearly.

6. All code must be clearly documented using comments.

7. Use diagrams and graphs where appropriate to clarify and/or enhance your answers.

1 Efficient and Stable Factorization of Anti-Symmetric Matrices (40 points)

We can solve a linear system of equation with an <-by-< symmetric positive-definite matrix � using the Cholesky factorization using 1

3< 3 + =(<3) arithmetic operations. The algorithm is backward stable and it is

about twice as efficient as an !* factorization with partial pivoting, which is also usually backward stable, but does not exploit symmetry. In some vague way it makes sense that Cholesky would be twice as efficient,

1

Linear Algebra Algorithms Exam

because due to the symmetry of the matrix, we can represent it using its upper and lower half, so we do not need to update the entire trailing submatrix after every elimination step.

In this problem we want to factor in a backward-stable a real matrix that is not symmetric, but satis- fies the constraint �) = −�. In other words, its elements satisfy �7 8 = −�87. We will call such matrices anti symmetric. Such matrices are fully defined by about <2/2 real values, not <2, so we hope to achieve computational savings similar to the savings in Cholesky.

The main building block in our new algorithm will be to zero most of the first column by subtracting a multiple of the second row of � from rows 3 : <. We will then zero most of the first row by subtracting the same multiples of the second column from columns 3 : <. We continue with the trailing submatrix in the same way, until we reduce � to a tridiagonal matrix) , in only sub- and super-diagonal elements)7+7,7,)7,7+1 are nonzero, and which is also anti symmetric.

1. Implement this algorithm and test it on random matrices with Gaussian elements. The algorithm should return twomatrices, a lower triangularmatrix !with 1s on the diagonal and an anti symmetric matrix ) , such that � satisfies � = !)!) (but a weaker condition in floating point). For simplicity, operate on all the elements of � and the trailing submatrices, not only on one triangle. Try to make the code as efficient as possible (while operating on both triangles). Test that it works correctly and explain how you performed the tests. Hint: As in !* with Gaussian elimination, if you eliminate column 8 with using a matrix !8 with ones on the diagonal and the negation of the multipliers below the diagonal in one column (which one?), thematrix ! should have themultipliers in the same position, but not negated.

2. Roughly how many arithmetic operation does your code perform? The answer should be given as an explicit multiple of <3; you can ignore low order terms. Please relate your answer to the number of operations that the !* factorization performs. Explain the result.

3. If you were to modify the algorithm and the code from Part 1 so that it would only operate on one triangle, say the lower one, howmany operations would the improved algorithm perform? How does this relate to the number of operations performed by the !* factorization?

4. The main motivation for this algorithm is that we can incorporate into it partial pivoting. Show that the algorithm, as presented up to now, can fail, and explain why it might be unstable even in cases where it does not fail.

5. We can avoid these problems by exchanging before we eliminate column 8 and row 8 two rows and the same two columns so that the element in position 8+1, 8 in the trailing submatrix has the largest mag- nitude among elements 8 + 1 : <, 8. We can express the overall factorization as %�%) = !)!) ,where % is a permutation matrix. Explain how these exchanges affect the matrix !. How do you think we can characterize the trailing submatrices and) if we perform these exchanges, both in the worst case and in practice? You only need to provide a reasonable characterization and to justify it from what we know about !* with partial pivoting; you do not need to provide a formal analysis.

6. We can make this algorithm even more efficient by noticing that the matrix � = )!) is upper Hes- senberg (elements �7 8 with 7 > 8 + 1 are zeros). Prove that this is indeed the case and explain how elements of ) relate to elements of � (so that we can construct ) from �).

7. Modify your code from Part 1 so that it computes ! and � . You can again update the entire trailing submatrix.

2

8. Explain how this modification reduces the number of arithmetic operations and give an estimate for the number of operations that the algorithm performs if it exploits the anti-symmetry (the leading term only).

9. To solve a system �F = %)!)!)%F = 1, we need to solve linear systems with a anti-symmetric tridi- agonal matrix) . Explain howwe can do that in a backward-stable way in$(<) arithmetic operations and storage.

2 Benchmarking Linear Solvers (30 Points) The aim of this problem is to benchmark a number of exiting solvers of linear equations. The focus is on producing valid and robust results and on presenting them well. For this problem, it is important that the solvers be efficient. Matlab is considered the gold standard for this problem. All its solvers are good enough (if used correctly); you can use some other programming environment (e.g., Python), but if one or more of its solvers is inefficient, you may lose points.

1. Implement a function lap2d that creates the Laplacian of an <-by-< two dimensional grid. Theweight of all edges should be 1, and the row-sums of all rows other than the first should be 0. The sum of the elements in the first row should be 1. The row/column ordering of the matrix should be a row- by-row ordering of the grid vertices (the so-called natural order). Thematrixmust be represented efficiently as a sparsematrix (inmatlab, the form S=sparse(i,j,a) is a goodway to construct the matrix from a set of nonzero values 07 8) Plot the nonzero structure of the matrix (spy) for a 10-by-10 grid.

2. Implement a similar function lap3d for 3-dimensional grids. Plot it for some convenient size for which the structure of the matrix is clear from the plot.

3. Write a code that measures the performance of several linear solvers for �F = 1, where � is a Lapla- cian from Part 1 and 1 is a random vector. You The solvers that you need to implement are:

(a) A dense Cholesky factorization. In Matlab, A=full(S) creates a dense representation of a sparse matrix.

(b) A sparse Cholesky factorization, with a row/column permutation to enhance sparsity in the factor. In Matlab, help chol (or the more detailed doc chol) will tell you how to invoke the Cholesky factorization so that it can permute the rows and columns of a sparse matrix.

(c) Conjugate gradients without a preconditioner (pcg in Matlab).

(d) Conjugate gradients with an incomplete-Cholesky factorization with no fill (ichol in Matlab).

4. Demonstrate that each of the solvers is correct. For the iterative solvers, explain their accuracy of the solution that they return and compare to the solution of the direct (Cholesky factorization) solvers. For the sparse solver, show the nonzero structure of the factor, to demonstrate that it is indeed sparse.

5. Compare the performance of the 4 solvers by finding out the size of the largest grid they can handle (in both 2D and 3D) in 10s (only the linear solver should take 10s; exclude the time to construct the test problem). You will need to write code that finds these problem sizes. You are free to also present the performance of the 4 solvers in other ways. Make sure your results are statistically robust; the

3

actual running times are not deterministic even if the algorithm is. You need not perform a statistical analysis, but you need to account for the running-times variability and to explain how do you did it. In this part of the problem, do your best to ensure that the solver is using only 1 CPU core (in Matlab, maxNumCompThreads(1) should work); explain how you restricted the solvers to 1 core and how you checked that they are indeed using only one.

6. Repeat Part 5, but with at as many cores as you can. Try to the speedups.

3 Efficient Multiplication of Sparse Matrices (20 Points) This problem investigates the efficient multiplication of sparse matrices represented using a compressed sparse column (CSC) representations. In this representation, the nonzero values of elements each column are stored consecutively in an array, and the row indices of these elements are stored in the same order in an integer array. These arrays need not be sorted in increasing row order. A third array points to the two arrays representing each column; this array represents the columns in increasing index order.

1. Given the CSC representation of two sparse matrices � ∈ R;×< and � ∈ R<×9, show how to create the CSC representation of the product �� in $(; + 9 + >) operations, where > is the number of arithmetic operations on nonzeros required to multiply the two matrices. Make sure you explain how to determine the size of each column in the product (that is, the size of the arrays that represent that column).

2. Given the CSC representation a sparse matrix � ∈ R;×<, show how to create the CSC representation of the product �) �. Try tomake this as efficient as possible and analyze the total number of operations that the multiplication requires in terms of ;, <, and >.

3. Suggest a mechanism to improve the efficiency of the solution of Part 1 in cases in which ; � >. That is, try to find a way to remove the dependence on ; from the running time.

4 A Tradeoff in the LLL Basis Reduction Algorithm (10 points) The !!! algorithm ensures that in the output matrix ‘ satisfies��’7,8�� ≤ 1

2 ��’7,7��

‘27,7 ≥ H’27−1,7−1 − ’27−1,7 .

for some 1/4 < H < 1. That is, the client code that calls LLL sets H to some value in this range. Explain the tradeoff: what happens when we set H just above 1/4? What happens when we set H just below 1?

• Implement and test the anti-symmetric matrix factorization algorithm.,

• Estimate arithmetic operations compared to LU factorization.,

• How many operations if operating only on one triangle?,

• Why can the algorithm fail and be unstable without pivoting?,

• How do row/column exchanges (pivoting) affect the factorization?