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

    \[\begin{equation} \int_{0}^1 log(x^4+1), \end{equation}\]

    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

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

    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.