multiphysicsProblemSet1Problem2.tex

%
% Copyright © 2014 Peeter Joot.  All Rights Reserved.
% Licenced as described in the file LICENSE under the root directory of this GIT repository.
%
\makeproblem{Resistor Mesh.}{multiphysics:problemSet1:2}{
\makesubproblem{
Write a small Matlab function that generates a netlist for a network made by:\(\cdots\)
\begin{enumerate}
\item
\( N \times N \) square grid of resistors of value R, where N is the number of resistors per edge. The grid nodes are numbered from 1 to \( (N +1)^2 \)
\item voltage source \( V = 1 V \) connected between node 1 and ground
\item
three current sources, each one connected between a randomly selected node of the grid and the reference node. The source current flows from the grid node to the reference node. Choose their value randomly between 10 mA and 100 mA;
\end{enumerate}
Generate the modified nodal analysis equations (1) for a grid with \( N = 50, R = 0.2 \Omega \) and solve them with your LU routine to find the node voltages. Plot the result with the Matlab command \matlabFunc{surf()}.
}{multiphysics:problemSet1:2a}
\makesubproblem{
}{multiphysics:problemSet1:2b}
Plot the CPU time taken by your system solver (LU factorization + forward/backward substitution) as a function of the size \(n\) of the 3 modified nodal analysis matrix \(\BG\). Note: do not exploit the sparsity of the matrix.
\makesubproblem{
Determine experimentally how the CPU time scales for large \(n\).  Fit the CPU times you observe with a power law like \(t_{\mathrm{cpu}} (n) \simeq K n^\alpha \) where \(K\) is a constant in order to determine the exponent \(\alpha\).
}{multiphysics:problemSet1:2c}
\makesubproblem{
Comment on the result. Discuss your findings in light of what we discussed in class
}{multiphysics:problemSet1:2d}
} % makeproblem
%
\makeanswer{multiphysics:problemSet1:2}{
\withproblemsetsParagraph{
\makeSubAnswer{}{multiphysics:problemSet1:2a}
%
The Matlab code for this problem is implemented in
%
\begin{itemize}
\item \nbcite{ps1:genResistorGridNl.m}{ps1/genResistorGridNl.m}
\item \nbcite{ps1:withPivotLU.m}{ps1/withPivotLU.m}
\item \nbcite{ps1:problem2driver.m}{ps1/problem2driver.m},
\end{itemize}
%
where the last is the driver callable with
\matlabFuncPath{problem2driver(0)}{ps1:problem2driver.m}.  This problem produces system equations \( G \Bx = \Bb \) that cannot be \( L U \) factored without pivots.  A more general (and slower) factorization routine that generates the factors \( G = L' U\), where \( P L' \) is lower triangular, and \( P \) is a permutation matrix is required.  This system can be solved with forward substitution for \( \By \)
%
\begin{equation}\label{eqn:multiphysicsProblemSet1Problem2:20}
P L' \By = P \Bb,
\end{equation}
%
then back substitution of
%
\begin{equation}\label{eqn:multiphysicsProblemSet1Problem2:40}
U \Bx = \By.
\end{equation}
%
% n(i,j)
For a system that has the random current sources specified in \cref{tab:multiphysicsProblemSet1Problem2:1}, the voltage surface plot for this network is plotted with \matlabFunc{surf()} in \cref{fig:ps1p2a:ps1p2aFig1}.
%
%\begin{tabular}[lll]
%\hline
%i & j & I mA \\
%\hline
%15 & 45 & 57 \\
%8 & 23 & 64 \\
%13 & 21 & 68 \\
%\hline
%\end{tabular}
%}
%
\captionedTable{Current sources.}{tab:multiphysicsProblemSet1Problem2:1}{
\begin{tabular}{|l|l|l|}
\hline
%\rowcolor[HTML]{CBCEFB}
%{\color[HTML]{000000} i} & {\color[HTML]{000000} j} & {\color[HTML]{000000} I (mA)} \\ \hline
i & j & I (mA) \\ \hline
15                       & 45                       & 57                            \\ \hline
8                        & 23                       & 64                            \\ \hline
13                       & 21                       & 68                            \\ \hline
\end{tabular}
}
%
% n(i,j) = 51(i-1) + j ; i = n % 51 ; j = n / 51
%I1 810 0 DC 0.057568
%I2 431 0 DC 0.0641784
%I3 684 0 DC 0.0688671
%
%ps1p2aFig1
\mathImageFigure{../figures/ece1254-multiphysics/ps1p2aFig1n50.pdf}{50 node resistor network plot.}{fig:ps1p2a:ps1p2aFig1}{0.3}{ps1:problem2driver.m}
%
\makeSubAnswer{}{multiphysics:problemSet1:2b}
%
All of the following plots and associated data for this question were generated with \matlabFuncPath{problem2driver(1)}{ps1:problem2driver.m}.
%
A plot of the cpu time vs node number is given in \cref{fig:ps1p2b:ps1p2bFig3}.
%ps1p2bFig3
\mathImageFigure{../figures/ece1254-multiphysics/problemBFitscpuTimeVsN.pdf}{Cpu times for range of grid sizes.}{fig:ps1p2b:ps1p2bFig3}{0.3}{ps1:problem2driver.m}
%
\makeSubAnswer{}{multiphysics:problemSet1:2c}
%
This power law fit can be recast as a linear fit of the log values.  Take logarithms of
%
\begin{equation}\label{eqn:multiphysicsProblemSet1Problem2:60}
t = \kappa n^\alpha,
\end{equation}
%
for
%
\begin{equation}\label{eqn:multiphysicsProblemSet1Problem2:80}
\ln( t ) = \ln \kappa + \alpha \ln n.
\end{equation}
%
For grid sizes \( n \in \{ 4,8,12,16,20,24,28,32,36,40,44 \} \), a fit
%
\begin{equation}\label{eqn:multiphysicsProblemSet1Problem2:n}
t(n) = 197 \times 10^{-6} n^{2.5}
\end{equation}
%
is found.  This linear fit of the log log plot of timings vs grid sizes is plotted along with raw data in \cref{fig:ps1p2c:ps1p2cFig4}.  The corresponding power fit and the original timing data is plotted in \cref{fig:ps1p2c:ps1p2cFig5}.
%
%ps1p2cFig4
\mathImageFigure{../figures/ece1254-multiphysics/problemBFitsLogFitCheckAndLogTotal.pdf}{Log log plot of timings vs grid sizes and its linear fit.}{fig:ps1p2c:ps1p2cFig4}{0.3}{ps1:problem2driver.m}
%
%ps1p2cFig5
\mathImageFigure{../figures/ece1254-multiphysics/problemBFitsFitCheckAndTotalTimes.pdf}{Power law fit with original timing data.}{fig:ps1p2c:ps1p2cFig5}{0.3}{ps1:problem2driver.m}
%
\makeSubAnswer{}{multiphysics:problemSet1:2d}
%
Notice that the linear fit is not actually a good match for large \( n \).
For small \( n \) the \( L U \) decomposition has \( O(2.4) \) time.
For large \( n \) the sparsity of the system generates a large amount of fill in work.
%
%\paragraph{Grading comment:}
%The problem statement says to not exploit sparsity, which makes the interpretation of the results more difficult.
%%
%There is no discussion on how your experimental findings related to what we see in class.
}
} % makeanswer