Homework Problems for Course Numerical …

Homework Problems for Course Numerical Methods for CSE

R. Hiptmair, G. Alberti, F. Leonardi Version of July 16, 2016

A steady and persistent effort spent on homework problems is essential for success in the course.

You should expect to spend 4-6 hours per week on trying to solve the homework problems. Since many involve small coding projects, the time it will take an individual student to arrive at a solution is hard to predict.

? The assignment sheets will be uploaded on the course webpage on Thursday every week.

? Some or all of the problems of an assignment sheet will be discussed in the tutorial

classes

on

Monday

1

1 2

weeks

after

the

problem

sheet

has

been

published.

? A few problems on each sheet will be marked as core problems. Every participant of the course is strongly advised to try and solve at least the core problems.

? If you want your tutor to examine your solution of the current problem sheet, please put it into the plexiglass trays in front of HG G 53/54 by the Thursday after the publication. You should submit your codes using the online submission interface. This is voluntary, but feedback on your performance on homework problems can be important.

? You are encouraged to hand-in incomplete and wrong solutions, since you can receive valuable feedback even on incomplete attempts.

? Please clearly mark the homework problems that you want your tutor to examine.

1

Prof. R. Hiptmair G. Alberti, F. Leonardi

AS 2015

Numerical Methods for CSE

Problem Sheet 0

ETH Z?rich D-MATH

These problems are meant as an introduction to EIGEN in the first tutorial classes of the new semester.

Problem 1 Gram-Schmidt orthogonalization with EIGEN

[1, Code 1.5.4] presents a MATLAB code that effects the Gram-Schmidt orthogonalization of the columns of an argument matrix.

(1a)

Based on the C++ linear algebra library EIGEN implement a function

t e m p l a t e < c l a s s Matrix> Matrix gramschmidt( c o n s t Matrix &A);

that performs the same computations as [1, Code 1.5.4]. Solution: See gramschmidt.cpp.

(1b) Test your implementation by applying it to a small random matrix and checking the orthonormality of the columns of the output matrix.

Solution: See gramschmidt.cpp.

Problem 2 Fast matrix multiplication

[1, Rem. 1.4.9] presents Strassen's algorithm that can achieve the multiplication of two dense square matrices of size n = 2k, k N, with an asymptotic complexity better than O(n3).

(2a)

Using EIGEN implement a function

1

MatrixXd strassenMatMult( c o n s t MatrixXd & A, c o n s t MatrixXd & B)

that uses Strassen's algorithm to multiply the two matrices A and B and return the result as output.

Solution: See Listing 1.

(2b)

Validate the correctness of your code by comparing the result with EIGEN's

built-in matrix multiplication.

Solution: See Listing 1.

(2c)

Measure the runtime of your function strassenMatMult for random matri-

ces of sizes 2k, k = 4, . . . , 10, and compare with the matrix multiplication offered by the

-operator of EIGEN.

Solution: See Listing 1.

Listing 1: EIGEN Implementation of the Strassen's algorithm and runtime comparisons.

1 # i n c l u d e 2 #include 3 #include

4

5 #include " timer .h"

6

7 using namespace Eigen ; 8 using namespace std ;

9

10 //! \brief Compute the Matrix product A ? B using

Strassen's algorithm.

11 //! \param[in] A Matrix 2k ? 2k

12 //! \param[in] B Matrix 2k ? 2k

13 //! \param[out] Matrix product of A and B of dim 2k ? 2k

14 MatrixXd s t r a s s e n M a t M u l t ( c o n s t MatrixXd & A , c o n s t

MatrixXd & B)

{ 15

16

i n t n=A . rows ( ) ;

17

MatrixXd C(n , n) ;

18

2

19

i f (n==2)

20

{

21

C ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download