Introduction to scientific Computing A Matrix Vector Approach Using Matlab Written by Charles FVan Loan 陈文斌 Wbchen(fudan. edu. cn 复日大学
Introduction to Scientific Computing -- A Matrix Vector Approach Using Matlab Written by Charles F.Van Loan 陈 文 斌 Wbchen@fudan.edu.cn 复旦大学
Matrix Computations Setting Up Matrix Problems Matrix Operations Once Again, Setting Up Matrix Problems Recursive Matrix Operations Distributed Memory Matrix Multiplication
Matrix Computations • Setting Up Matrix Problems • Matrix Operations • Once Again, Setting Up Matrix Problems • Recursive Matrix Operations • Distributed Memory Matrix Multiplication
Ax=b Matrix-vector multiplication Matrix- Matrix multiplication Often the amount of work that is required to initialize an n-by-n matrix is as much as the work required to solve forx Fast fourier trans form and fast strassen matrix multiply algorithm
• Matrix-vector multiplication • Matrix- Matrix multiplication • Often the amount of work that is required to initialize an n-by-n matrix is as much as the work required to solve for x • Fast Fourier transform and fast Strassen matrix multiply algorithm Ax=b
Setting up Matrix problems
Setting up Matrix problems
Hilbert matrix A=zeros(n,n) a=zeros(n,n) for i=1: n for i=l,n for i=l: n for j=i:n A(ij=1/(i+j-1); Simple j Recipes A(ij)=1/(i+j-1) AG, D=A(i,j ene end en
Hilbert matrix 1 1 + − = i j aij A=zeros(n,n); for i=1:n for j=1:n A(i,j)=1/(i+j-1); end end A=zeros(n,n); for i=1:n for j=i:n A(i,j)=1/(i+j-1); A(j,i)=A(i,j); end end Simple ij Recipes
function H=hilb(n) %HILB Hilbert matrix This is also a good example of efficient MaTlaB programming %o style where conventional for or do loops are replaced b %o vectorized statements. This approach is faster, but uses more storage % C Moler. 6-22-91 %o Copyright 1984-2001 The Math Works, Inc % PRevision:59$ SDate:2001/04/1512:02:29 J=l n; J=J(ones(n, D) :I=J E=ones(n, n H=E/(I+J-1)
function H = hilb(n) %HILB Hilbert matrix. % This is also a good example of efficient MATLAB programming % style where conventional FOR or DO loops are replaced by % vectorized statements. This approach is faster, but uses % more storage. % C. Moler, 6-22-91. % Copyright 1984-2001 The MathWorks, Inc. % $Revision: 5.9 $ $Date: 2001/04/15 12:02:29 $ J = 1:n; J = J(ones(n,1),:); I = J'; E = ones(n,n); H = E./(I+J-1);
The setting up of a matrix can often be made more efficient by exploiting relationships that exist between the entries. ifo<ksm k k-1 k!(m-k)! 0 otherwise O(n)flops 1000 Pii= pi-li-Itp 1100 P O(n) flops 1331
The setting up of a matrix can often be made more efficient by exploiting relationships that exist between the entries. = − − − = 0 otherwise if 0 !( )! ! 1 1 k m k m k m k m pmk O(n3 ) flops = 1 3 3 1 1 2 1 0 1 1 0 0 1 0 0 0 P pi j = pi−1, j−1 + pi−1, j O(n2 ) flops
P=zeros(n,n) P(:,1)=ones(n1) O(n2) flc for i=2 ops for 1=2 P(1)=P(-13-1)+P(-1) end
P=zeros(n,n); P(:,1)=ones(n,1); for i=2:n for j=2:i P(i,j)=P(i -1,j -1)+P(i -1,j); end end O(n 2) flops
Matrix defined by a vector ofparameters 2之J 2 4 Length(x,y) V(:,1)=ones(n,1) for j=2: n V(:j)x*V(:-1); end
= 3 4 2 4 4 3 3 2 3 3 3 2 2 2 2 3 1 2 1 1 1 1 1 1 x x x x x x x x x x x x V Matrix defined by a vector of parameters n=length(x,y); V(:,1)=ones(n,1); for j=2:n V(:,j)=x.*V(:,j-1); end
Circulant C=as d9 aa a1 matrices 4 2 function C=Circulant1(a) function C=Circulant2(a) n=length(a);C=zeros(n,n);n=length(a); C=zeros(n,n) for i=l: n C(1,)=a; for j=l:n for j=2: n C(i j)=a(rem(n-i+j, n)+1); C(is )=[C(i-1, n)C(i-1, 1: n-1) end end ((n-i+j)mod n)+1 ent
= 2 3 4 1 3 4 1 2 4 1 2 3 1 2 3 4 a a a a a a a a a a a a a a a a C Circulant matrices function C = Circulant1(a) n = length(a); C = zeros(n,n); for i=1:n for j=1:n C(i,j) = a(rem(n-i+j,n)+1); end end function C = Circulant2(a) n = length(a);C = zeros(n,n); C(1,:) = a; for i=2:n C(i,:) = [ C(i-1,n) C(i-1,1:n-1) ]; end i j = a((n−i+ j)mod n)+1 c