# Homework 2, due in class 2016-02-05¶

Software Search

• Variation on question 2.1 from Demmel. Point your browser to www.netlib.org and find a Fortran routine that approximates the integral

$$$\int_{0}^1 log(x^4+1),$$$

using a 31-point Gauss-Kronrod quadrature. Bonus points if you can use the subroutine as well.

BLAS

• Write your own matrix-matrix multiplication routine for square matrices of size $$n \times n$$ and compare the execution time with DGEMM (and if you use Fortran the intrinsic matmul routine) for matrices with $$n=1, 2, \ldots, 1500$$. In addition to tabulating the runtimes also provide megaflops.

Gauss Elimination

• So far we have not considered pivoting and we must therefore be a bit careful with choosing our matrices. Prove that if a nonsingular matrix $$n \times n$$ matrix $$B$$ is diagonally dominant by column, then the LU decomposition can be computed without pivoting. Also prove that the multipliers satisfy $$|l_{i,j}| \le 1$$, for $$i \le j < i \le n$$. Hint: read Error Analysis of Direct Methods of Matrix Inversion, J. H. Wilkinson, Journal of the ACM, Volume 8 Issue 3, 1961.

• In Algorithm 1 (as discussed in class) we access the elements of $$A$$ in row-wise order. Modify the algorithm so that the innermost loop involves a fixed column index and a varying row index instead.

• Compare the execution speed of the two algorithms. How does it compare to a theoretical estimate combined with the performance data of your CPU?

• Use Algorithm 1 to solve $$Ax=b$$ where $$A$$ is the $$n \times n$$ matrix that has diagonal entries 2 and sub- and super-diagonal entries 1.01. Consider the right hand side $$b^T = (1,1,1,\ldots,1)$$ and plot the relative error in the solution as a function of $$n$$. Use DGESV or backslash to compute the exact solution.

• Let

$$$A = \left( \begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array} \right),$$$

where $$A_{11}$$ is $$k \times k$$ and nonsingular. Then $$S = A_{22} - A_{21}A{11}^{-1}A_{12}$$ is called the Schur complement of $$A_{11}$$ in $$A$$.

1. Show for small example that after $$k$$ steps of Gaussian elimination without pivoting $$A_{22}$$ has been overwritten by $$S$$.
2. Suppose $$A=A^T$$, $$A_{11}$$ is positive definite and $$A_{22}$$ is negative definite. Then GE without pivoting works in exact arithmetic. Construct a $$2 \times 2$$ example satisfying these assumptions where GE is numerically unstable. That is, find an example where the computed factors using floating point arithmetic, $$\hat{L}$$, $$\hat{U}$$ satisfy $$\hat{L}\hat{U} = A+E$$ where $$\|E\|$$ is not small compared to $$\|A\|$$ in some standard matrix norm.

UL Factorization

• Write a program that computes the factorization $$UL=A$$.

Gerschgorin Circles

• The assumption that $$B$$ is nonsingular is actually superfluous. Show that diagonally dominant by column implies invertibility.