Problem of the Day
Aug 26 Here is a talk and a paper that discusses the polygon averaging problem. The matrix M_{n} plays a critical role, e.g.,
M_{4} = .5*[1 1 0 0; 0 1 1 0; 0 0 1 1; 1 0 0 1]
What would the "M" matrix look like if we took an arbitrary convex combination of vertices instead of their average, i.e.,
xNew(k) = mu* x(k) + (1-mu)*x(k+1) 0 < mu < 1
instead of xNew(k) = (x(k)+x(k+1))/2. Feel free to play around with PolyAve.m to see what the impact would be with this generalization. (Visit the computation of xNew and yNew in the subfunction Smooth.)
--------------------
Aug 28 This will get you thinking about rows, columns, and blocks and how to "grab 'em" in Matlab. Write a Matlab function Sudoku(A) that returns "1" if A is a valid Sudoku solution and zero otherwise. Thus, A must be a 9x9 matrix with the property that every column, row, and 3x3 block is made up of the integers 1 through 9.. Hints on checking. If sort(A(5,:)) is the same as 1:9, then row 5 is "OK". If B= A(4:6,7:9) and sort(B(:)) is the same as (1:9)', then the (2,3) block is OK. Some built-in functions that you may find useful: sort, sum, any, all
--------------------
Aug 31 This problem is about "spotting" matrix-vector operations given some awful-looking multiple summation with subscripts all over the place. As a warm-up, take a look at problem 1.1.6 in GVL4. Now here is the problem. Assume that A is nxn and that u, x, y, z, and d are column n-vectors of reals. Assume that v is a permutation of 1:n. Rewrite the following O(n^4) algorithm so that it is O(n^2):
alfa = 0 |
for i = 1:n |
for j = 1:n |
for p = 1:n |
for q = 1:n |
alfa = alfa + A(i,p)*A(v(j),q)*u(i)*y(j)*x(q)*z(p)*d(i) |
end |
end |
end |
end |
A handy test script SpotMatVec is available.
-------------------
Sep 2 Without using Matlab, what is the SVD of the 2x2 matrix A = [ 3 4 ; 8 -6] ?
--------------------
Sep 4 The Haar matrix W_n is defined in terms of W_m where n = 2m and W_{1} = [1]:
W_n = [ kron(W_m , [1;1]) kron(I_{m},[1;-1]) ]
Can you develop a closed form expression for the number of nonzeros in W_n ?
--------------------
Sep 9 Get solid with the floating representation. Understand fpFacts.m. Give a recipe for the largest positive integer k such that 10^k can be represented EXACTLY in IEEE double precision. Hint: How many bits are in the binary expansion of 5^k. Give a recipe for the largest positive integer k such that k! can be represented EXACTLY in IEEE double precision. Hint: 6! = 1*2*3*4*5*6 = 45*(2^4)
--------------------
Sep 11 Assume L1 and L2 are nxn, lower triangular, and nonsingular. Assume that B is nxn. How would you compute an nxn matrix X so that L1*X*L2' = B using the \ operator? Hint. How would you do it if L2 = I? (How would you do it if L1 = 0?) Now assume the availability of a function x = LTriSol(L,b) that returns the solution to the lower triangular system Lx = b where b is a column vector. How would you compute X using LTriSol?
--------------------
Sep 14 A and B are nxn matrices and A is nonsingular. Assume that b and c are column n-vectors. How would you use the Matlab lu function and \ operator to solve the 2n-by-2n linear system [A B ; zeros(n,n) A' ] [y ; z] = [b ; c]?
--------------------
Sep 16 (a) Assume nxn matrices A1 and A2 are differ only in their last columns. Assume that lu(A1) produces P1*A1 = L1*U1 and that lu(A2) produces P2*A2 = L2*U2. Describe the differences between P1 and P2, L1 and L2, and U1 and U2. (b) Assume that A is a singular nxn matrix and that PA = LU. Assuming exact arithmetic, how could a unit 2-norm vector z be found so that Az = 0.
--------------------
Sep 18 Modify the function BlockLU so that it reports back the fraction of flops that are level-3 flops. Modify it again so that it is nonrecursive.
--------------------
Sep 21 Assume that we have computed the Cholesky factorization A = GG' of a symmetric positive definite nxn matrix A. Let k be an integer that satisfies 1<=k<n. Recall that A(k,k) is positive and that A(1:k,1:k) is also sym pos def. What is the smallest smallest positive tau for which A - tau*ek*ek' is not positive definite? Here, ek = I(:,k). In plain English, we want to subtract "just enough" stuff from the (k,k) entry so that A loses definiteness.
--------------------
Sep 23 A is symmetric positive definite and tridiagonal. If A = LDL' and D = diag(d), how would you compute a vector x so that x'*A*x = d(k)?
--------------------
Sep 25 Suppose Tn = Gn*Gn' is the Cholesky factorization of Tn, the -1,2,-1 tridiagonal matrix. Gn is lower bidiagonal. What can you say about the entries Gn(n,n) and Gn(n,n-1) as n-->infty?
--------------------
Sep 28 Under what conditions does the Gauss-Seidel iteration converge when A = [a b; c d]? Repeat for the Jacobi iteration.
--------------------
Sep 30
--------------------
Oct 2 Suppose A = [ d1 e; e d2] is positive definite. What is the condition of this matrix? Now let Atilde = inv(D)Ainv(D) where D = diag(sqrt(d1),sqrt(d2)). What is the condition of Atilde? This is an issue because the latter condition nember determines how quickly PCG converges with D as a preconditioner.
--------------------
Oct 5 (a) For the 3-by-2 case, verify that the method of normal equations is equivalent to zeroing the gradient of
f(x) = (A*x - b)'*(A*x - b)
(b) Given matrices A1 (m1xn), A2 (m2xn) and A3 (m3xn) and vectors b1 (m1x1), b2 (m2x1) and b3 (m3x1), how would you compute a vector x that minimizes || A1*x - b1 ||^2 + || A2*x - b2 ||^2 + ||A3*x - b3 ||^2? (c) Given [Q,R] = qr(A,0), how would you compute the minimum value of || Ax -b|| ?
---------------------
Oct 7 Given A (mxn) and b (mx1), how would you compute the closest vector to b that is orthogonal to every column of A? (b) Given that Q = [c s;s -c] is orthogonal, how would you compute a unit vector u (2x1) so that Q = I-2u*u'?
--------------------
Oct 9 Suppose f and g are column n-vectors. Show how to compute an orthogonal Q as a product of Givens rotations so that Q' * (f * g') * Q is zero everywhere except in the (1,1) and (1,2) entry. Hint. Put a lot of zeros into f and then put a lot of zeros in g.
--------------------
Oct 14 (a) What can you say about Q, R, and P if [Q,R,P] = qr(A) and A has more columns than rows. (b) Assuming that A has full row rank, how could you use Q, R, and P to compute a solution to Ax = b?
--------------------
Oct 16 Suppose A is mxn with full column rank and that b is mx1. How would you minimize || Ax - b|| subject to the constraint that x(1) +...+ x(n) = 0?
---------------------
Oct 19 Suppose A and B are are 2x2 and that det(A)det(B) < 0. How would you compute Q = [c s;-s c] so that norm(A - BQ,'fro') is minimum?
--------------------
Oct 21 This is about the case when the TLS problem has no solution. Show that if the smallest singular value of [A b] is unique and equals the smallest singular value of A, then the TLS problem has no solution. Use this result to show that if A'*b = 0 and norm(b) > sigma_min(A), then the TLS problem has no solution.
Mar 13 Let A = [lambda_1 m ; 0 lambda_2] and assume that the eigenvalues lambda_1 and lambda_2 are distinct. Determine X so inv(A)*A*X = diag(lambda_1,lambda_2). Recall that if Ax = lambda* x and y'*A = lambda*y' then the condition of lambda is 1/abs(x'*y) assuming that x and y have unit 2-norm. What is the condition of lambda_1 and lambda_2 in the above 2-by-2 example? More generally, how would you compute the condition number of all the eigenvalues using [X,D] = eig(A) assuming that the eigenvalues of A are distinct?
Mar 9 If A-sI = QR, why is B = RQ +sI similar to A?
Mar 6 Write a fragment to handle the update A = H'*A*H where H = I - 2*u*u' with u(1:r) = 0. Assume A is symmetric.
Mar 4
Mar 2 Show that after a Jacobi update that zeros A(p,q), then off(Anew)^2 = off(A)^2 - 2A(p,q)^2. Here, off(A)^2 is the sum of the squares of the off-diagonal entries.
--------------------
Oct 23 Suppose Q'*A*Q = diag(d1,d2) is the schur decomposition of a symmetric 2x2 matrix A. Why is it always possible to choose Q so that det(Q) = -1?
--------------------
Oct 26 Suppose Ax = lambda*x is the dominant eigenpair for a symmetric A. What happens if we apply the power method with the matrix A - lambda*x*x' ?
--------------------
Oct 28 If you have a function [c,s] = Schur2(A) that computes a rotation that diagonalizes a symmetric 2-by-2 A, show how it can be used to compute a 2-by-2 svd. Hint: How would you determine c and s so that [c s;-s c]'*[w x ; y z] is symmetric.?
--------------------
Oct 30 Suppose A is nxn and symmetric. How would you compute an nxk matrix Q with orthonormal columns so that trace(Q'*A*Q) is maximized.?
--------------------
Nov 2 Suppose Ax = mu*x + r where x has unit 2-norm. Use the Wielandt-Hoffman theorem to prove that mu is within norm(r,2) of an exact eigenvalue.
--------------------
Nov 4 In the Householder tridiagonalization Q'*A*Q = T, the first column of Q is the first column of I. Explain. Now suppose v is a unit vector.How would you compute an orthogonal U so that (a) Uv = + or - I(:,1) and (b) U'*A*U is tridiagonal.
--------------------
Nov 6 Suppose A = I + UDU' where U is n-by-k and D is kxk. If q is a unit vector, what can you say about the rank of [q, Aq, A^2*,..,A^(n-1)q]?
--------------------
Nov 9 Let A = [lambda_1 m ; 0 lambda_2] and assume that the eigenvalues lambda_1 and lambda_2 are distinct. Determine X so inv(A)*A*X = diag(lambda_1,lambda_2). Recall that if Ax = lambda* x and y'*A = lambda*y' then the condition of lambda is 1/abs(x'*y) assuming that x and y have unit 2-norm. What is the condition of lambda_1 and lambda_2 in the above 2-by-2 example? More generally, how would you compute the condition number of all the eigenvalues using [X,D] = eig(A) assuming that the eigenvalues of A are distinct?
--------------------
Nov 11 A is a real matrix and mu is a complex eigenvalue. Suppose Az = mu*z. Show that the real and imaginary parts of the (complex) eigenvector z define a real, 2-dimensional invariant subspace. Suppose the dominant eigenvalue lambda_1 of a real matrix is complex. Note that the conjugate of lambda_1 is also an eigenvalue so the dominant eigenvalue is not unique. What happens if we apply the power method with a real starting vector? Assume that all the other eigenvalues are smaller in maginitude.
--------------------
Nov 13 Suppose x and y are unit 2-norm n-vectors. How would you choose mu so that ||A*x-m*x||^2 + ||A'*y - mu*y||^2 is minimized?
--------------------
Nov 16
--------------------
Nov 18
--------------------
Nov 20
------------------
Nov 23
--------------------
Nov 30
--------------------
Dec 2
--------------------
Dec 4
--------------------