%% -*- mode: latex; coding: utf-8 -*- \documentclass[a4paper, 10]{article} % This document is (C) and ©, Mahindra École Centrale, 2014,15 % Written by Lilian Besson (https://bitbucket.org/lbesson/) for the MA 101 course (2014). %% Well understand input, and nice output \usepackage[english]{babel} \usepackage[utf8]{inputenc} \usepackage{lmodern} \usepackage[T1]{fontenc} \usepackage{cmap,enumerate,multicol} % {fixltx2e} \usepackage{amsmath,amsfonts,amssymb,amsthm,bbm,mathabx} \usepackage{mathrsfs,graphicx,xcolor,color,float,framed,scrextend} \everymath{\displaystyle} \usepackage{enumitem} % use {enumerate} if enumitem is not available \usepackage{listings} % Include Python code! (and any other language) \usepackage{textcomp} % Thanks to http://tex.stackexchange.com/a/50538 (\textquotesingle{} can be used to input ') \usepackage[scale=0.78]{geometry} \newcommand{\inv}[1]{\frac{1}{#1}} \newcommand{\mytitle}[0]{CS101 project : matrices and linear operations} \usepackage{fancyhdr} \pagestyle{fancyplain} \renewcommand{\headrulewidth}{0.2pt} \renewcommand{\footrulewidth}{0.2pt} %% If necessary, change here the header and footer \lhead{\it{\mytitle{}}} %% Left header \chead{\fancyplain{}{\href{http://www.MahindraEcoleCentrale.edu.in/portal/course/view.php?id=27}{\textbf{CS101}}}} %% Center header \rhead{\it{\today}} %% Right header \lfoot{\small{Please, report any issue to \href{mailto:CS101_at_crans_._org}{\texttt{{CS101}{@}{crans.org}}}}} %% Left footer % \cfoot{\thepage/\pageref{LastPage}} %% Center footer \rfoot{\tt{\href{http://www.MahindraEcoleCentrale.edu.in/}{Mahindra École Centrale}}, 2015} %% Right footer \usepackage[plainpages=false,pdfcenterwindow=true, pdftoolbar=false,pdfmenubar=false,backref, pdftitle={\mytitle{}}, %% If necessary, change here the default PDFAuthor value pdfauthor={Mahindra École Centrale, Hyderabad, Telangana}, linkcolor=black,citecolor=black,filecolor=black,urlcolor=black]{hyperref} %% Allow to add URL hyperlink with the command \href. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Code embedding. %% Custom colors for code embedding. \definecolor{dkgreen}{rgb}{0,0.4,0} \definecolor{gray}{rgb}{0.5,0.5,0.5} \definecolor{purple}{rgb}{0.58,0,0.82} %% From https://en.wikibooks.org/wiki/LaTeX/Source_Code_Listings#Customizing_captions \lstset{ % backgroundcolor=\color{white}, % choose the background color; you must add \usepackage{color} or \usepackage{xcolor} basicstyle=\ttfamily, % \texttt\small, % the size of the fonts that are used for the code, FIXME \ttfamily breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace breaklines=true, % sets automatic line breaking captionpos=b, % sets the caption-position to bottom commentstyle=\small\color{dkgreen}\emph, % comment style % deletekeywords={...}, % if you want to delete keywords from the given language % escapeinside={\%*}{*)}, % if you want to add LaTeX within your code % extendedchar=true, % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8 frame=single, % adds a frame around the code keywordstyle=\small\color{blue}, % keyword style language=python, % the (default) language of the code fontadjust=false, % if you want to add more keywords to the set % morekeywords={define,domain,objects,init,goal,problem,action,parameters,precondition,effect,types,requirements,strips,typing}, numbers=left, % where to put the line-numbers; possible values are (none, left, right) numbersep=10pt, % how far the line-numbers are from the code numberstyle=\small\color{gray}, % the style that is used for the line-numbers rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here)) showspaces=false, % show spaces everywhere adding particular underscores; it overrides 'showstringspaces' showstringspaces=false, % underline spaces within strings only showtabs=false, % show tabs within strings adding particular underscores stepnumber=1, % the step between two line-numbers. If it's 1, each line will be numbered stringstyle=\small\color{purple}, % string literal style tabsize=4, % sets default tabsize to 2 spaces prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}}, % pour la fin des lignes. aboveskip={0.5\baselineskip}, belowskip={0.5\baselineskip}, %title=\lstname % show the filename of files included with \lstinputlisting; also try caption instead of title % title=\tiny{File \textcolor{blue}{\url{\lstname}}} % show the filename of files included with \lstinputlisting; also try caption instead of title %% FIXME title ! upquote=true % Thanks to http://tex.stackexchange.com/a/50535 } \begin{document} \numberwithin{equation}{section} %% Option to number equations \DeclareGraphicsExtensions{.pdf,.png,.jpg,.svg} %% Order to load the images \title{\mytitle{}} %% Define Title of the document %% -*- coding:utf8; mode:latex -*- %% LaTeX file automatically generated with [strapdown2pdf](https://bitbucket.org/lbesson/bin/src/master/strapdown2pdf) %% from /home/lilian/cs101/projects/index.html, the jeudi 12 mars 2015, 15:36:29 (UTC+0530). \section*{Instructions for the programming project} This document is explaining to you what you will have to do (and how you will do it) for the CS101 programming project in $2014/15$ at \emph{Mahindra École Centrale}. \paragraph{Topic:} You and your team-mates will work on matrices and linear algebra operations. % This is not something new, as we are using examples from MA102 since February, but you will have a lot to do. % The goal of this project is to use concepts from OOP (as taught by Prof. Vipin) in order to be able to perform linear algebra operations in a really natural manner. % At the end, you will be able to define, read and modify matrices with a syntax close to maths (\texttt{A[i, j]}), and compute determinant, rank, trace, inverse with \texttt{A.det()} or \texttt{matrix.trace(A)}, and compute inverse with \texttt{A**(-1)} or \texttt{A.inv()}. \paragraph{General instructions:} Please refer to the main document we gave you, it contains general advices, details about the deadline, and tells you how to submit your work. \hspace{\fill}\rule{.6\linewidth}{0.4pt}\hspace{\fill} \section{What do you have to do?} \subsection{In a file called \texttt{matrix.py}} \begin{enumerate} \item Define a class \texttt{Matrix} to represent (n, m) matrices. As previously, implement matrix as list of lists. The \texttt{\_\_init\_\_} method should be defined like this : \texttt{def \_\_init\_\_(self, M)} where \texttt{M} is a list of row vectors. This list of list \texttt{M} will be stored in an attribute called \texttt{listrows}. Here is a snippet of code from where you can start: \begin{lstlisting}[language=python] # In the file matrix.py class Matrix(): """ Represents matrices of size (n, m). """ def __init__(self, M): """ Create a matrix from the list of row vectors M. """ self.listrows = M self.n = len(M) self.m = len(M[0]) ... # keep working from that point \end{lstlisting} \item \href{https://bitbucket.org/lbesson/mpri-bomberman/src/master/Matrix.py\#cl-207}{First, define a method called \texttt{\_\_getitem\_\_}} (with \texttt{def \_\_getitem\_\_(self, i, j)} in the \texttt{Matrix} class body) to authorize reading the $(i, j)$ value of \texttt{A.listrows} with a syntax as simple as \texttt{A[i,j]}. \item Then define as many \textbf{special methods}\footnote{ Special methods names are between double underscores : \texttt{\_\_init\_\_}, \texttt{\_\_getitem\_\_} or \texttt{\_\_add\_\_}. They are used to modify the way Python interprets its command.} as you need, in order to be able to manipulate \texttt{Matrix} objects easily. A list of such method can be found at \href{https://docs.python.org/2/reference/datamodel.html\#emulating-numeric-types}{docs.python.org/2/reference/datamodel.html\#emulating-numeric-types} or \href{https://docs.python.org/2/library/operator.html}{docs.python.org/2/library/operator.html}. \item At least, implement the sum, difference, multiplication, and integer power for matrices, by using the respective special method. For instance, \texttt{def \_\_add\_\_(self, B)} will define the method \texttt{A.\_\_add\_\_}, which is called when we ask to compute the matrix $A + B$ : \texttt{A + B} is computed by calling \texttt{A.\_\_add\_\_(B)}. \item Write a function \texttt{rand\_matrix(n, m, K)} for generating a random matrix (ie. instance of the Matrix class) of size $(n, m)$ with each coefficients being integers, randomly taken between $-K$ and $K$. %(as it was done in lab). \item Define a function \texttt{gauss} in the module \texttt{matrix.py}, and then use it to add a method \texttt{A.gauss()} to the class \texttt{Matrix}. This function will apply the \textsc{Gauss} elimination algorithm to the matrix self (use the reference algorithm on Wikipedia if needed : \href{https://en.wikipedia.org/wiki/Gaussian\_elimination}{en.wikipedia.org/wiki/Gaussian\_elimination}). \item Use the \textsc{Gauss} algorithm to write a function (and a method) \texttt{det} that compute the determinant. Hint: you might have to adapt the previous function a little bit (cf. MA102 or Wikipedia). \item Similarly, use the \textsc{Gauss} method or function to write a function and a method \texttt{rank} for computing\footnote{ The result to use has been seen in MA102, and is also on \textsc{Apostol}, Vol.II.} the rank of the matrix. \item Write a few utility functions, like \texttt{ones(n, m)} and \texttt{zeros(n, m)} which make a $(n, m)$ matrix filled of $1$ or $0$, \texttt{eye(n)} for the $(n, n) $identity, \texttt{diag(d)} which takes a $n$-sized vector $\mathbf{d} = (d_1, \dots, d_n)$ and creates a matrix with these values $d_i$ on the diagonal etc. You can include any function which seems useful, of course. \end{enumerate} \subsection{In a file called \texttt{tests.py}} \begin{enumerate} \item Write \emph{at least two examples} (of different size) for \emph{every} method or function you implemented in the \texttt{matrix.py} file. \item Do not use random matrix ! We need to check that the examples are computed correctly. \item For example, this \texttt{tests.py} file will look like this: \begin{lstlisting}[language=python] import matrix A = matrix.Matrix( [ [1, 2], [3, 4] ] ) print "A =", A B = matrix.Matrix( [ [5, 6], [7, 8] ] ) print "B =", B print "A + B =", A + B # uses A.__add__(B) print "A * B =", A * B # uses A.__mult__(B) print "A ** 13 =", A ** 13 # uses A.__pow__(13) # many more to do ! print "det(A) =", A.det() # uses the method A.det() print "det(B) =", matrix.det(B) # calls the function matrix.det(B) \end{lstlisting} \item Feel free to get examples from the MA102 course, like the examples seen in lectures, or the problems in either the exams or the tutorial sheets. Any interesting examples that you want to illustrate or compute in your project will help you having a better mark. \end{enumerate} \subsection{In your project report} \begin{itemize} \item Explain any choice or special hypotheses you chose to follow for all the algorithms you implemented (especially \textsc{Gauss}, exponentiation, \textsc{Gram-Schmidt}, det and rank if you implement them). \item If you choose to implement any extra features to the \texttt{matrix.py} file (it can be an extra function or method), please explain it in details in your report. \item For \emph{each} function and method you write, give its time complexity ($O(n), O(n^2)$ etc) in its \emph{docstring}\footnote{ A good example of such practice is \href{https://bitbucket.org/lbesson/python-demos/src/master/CS101_Second_Mid-Term_Exam__Problem_II.py\#cl-74}{the solution for Problem III for CS second mid term exam} (given on Moodle).}. \end{itemize} \hspace{\fill}\rule{.6\linewidth}{0.4pt}\hspace{\fill} \section{Possible extra job?} Any of the following task will give you extra marks\footnote{ It is not possible to aim the best mark without trying any of these$\dots$}. \begin{enumerate} \item Implement the \textsc{Gram-Schmidt} process\footnote{ Reference is page 22 of \textsc{Apostol}, Vol.II, Theorem 1.13, or on Wikipedia.} for the usual dot product (which can be defined with \texttt{def dot(vx, vy):~return sum([ x \textcolor{red}{*} y for x,y in zip(xv,xy)])}). The family of $n$ vectors $(x_1, \dots, x_n)$ of $\mathbb{R}^n$ will be given as a matrix $A$ of size $(n, n)$. You \underline{have to chose and specify} if the $(x_k)$ are rows or columns of this matrix. \item Look for any method to solve a (square or not) linear system $A . x = b$ (e.g. \textsc{Cramer} formula, or \textsc{Gauss} elimination). Chose one algorithm and implement\footnote{ Its \underline{correctness} will be \textbf{more important} than its \underline{complexity}.} it. \item After having implemented the \textsc{Gauss} elimination algorithm, try to also write the \textbf{\textsc{Gauss-Jordan} elimination} (which goes further, to obtain a \emph{reduced} row echelon form). \item The \textsc{Gauss-Jordan} elimination can then be used\footnote{ This result has also been seen in MA102, and is in paragraph 2.19 of \textsc{Apostol} Vol.II, page $66-67$.} to compute $A^{-1}$ when $A$ is invertible (ie. non-singular). Use this algorithm to implement the \texttt{A.inv()} method, and to compute negative integer power : $A^{-k} = \left(A^{-1}\right)^k$ (you should update the \texttt{\_\_pow\_\_} method for the class \texttt{Matrix}). \item For all your functions and methods, you can take the time to check that the given arguments are valid. For example, $n, m$ should always be non-negative. \underline{Hint:} it is easy to perform such checks, by using the \texttt{assert} keyword. Example: \texttt{assert n > 0 and m > 0} check that $n > 0$ and $m > 0$. \end{enumerate} \subsection{Bonus: overloading the \texttt{+}, \texttt{-}, \texttt{*}, \texttt{/}, \texttt{\%} operators to accept numbers also} If you want to try, by using a simple test \texttt{isinstance(B, Matrix)} (to know if \texttt{B} is a matrix or not), it is possible to generalize the \texttt{\_\_add\_\_}, and the other special methods, in order so that they can accept (float/int/complex) numbers in which case the operation is done coefficient-wise. \underline{Example:} \texttt{Matrix([[1, 2], [3, 4]]) + 2} is \texttt{Matrix([[3, 4], [5, 6]])}. \subsection{Bonus: eigen values and vectors \textbf{(Harder!)}} \begin{itemize} \item \textcolor{red}{Try to} implement an algorithm to compute the spectrum (ie. set of eigen values) for a square matrix. \item Is it reasonable to try to obtain an \emph{exact} solution in the general case (for any $n$, and not just $n < 5$) ? \item Similarly, \textcolor{red}{try to} find and implement an algorithm to find eigen vectors. \end{itemize} \underline{Hint:} this bonus question is quite hard, do not spend too much time on it. \hspace{\fill}\rule{.6\linewidth}{0.4pt}\hspace{\fill} \section{Extra advices} \begin{itemize} \item Each function or method should be correctly implemented. The \emph{correctness} of everything you write \emph{is crucial} (the required examples are in fact here to help you detect any issue). \item Be careful about the special cases (empty lists, division by zero, integer division etc). \item Do not cheat from your friends or from Internet. %%, I will detect it. \item Apply the rule ``the more efficient, the better'' for each function/method you write. Do not try to optimize each line, what is important is the \emph{overall complexity} of the algorithms (e.g. $O(\log(k) n^3$) is better than $O(k n^3)$). You can take some ideas from the exams or the labs. \item But keep in mind that \emph{readability and simplicity of your programs are important}! \item Please contact me if needed (\texttt{{CS101}{@}{crans}{.}{org}} or \texttt{{Lilian}{.}{Besson}{@}{ens}{-}{cachan}{.}{fr}}). \end{itemize} \hspace{\fill}\rule{.6\linewidth}{0.4pt}\hspace{\fill} \newpage{} \section{Linear algebra packages in Python} Of course, all this has already been written in Python. The goal is not to use these packages, but \underline{to implement this \texttt{Matrix} class, and all these algorithms by yourself.} If you are curious, you can compare your results with the ones obtained with one of the following package. \subsection{With \textbf{NumPy}} \href{http://docs.scipy.org/doc/numpy/reference/routines.linalg.html}{docs.scipy.org/doc/numpy/reference/routines.linalg.html} for linear algebra operations with the \href{http://docs.scipy.org/doc/numpy/}{NumPy} module (Numerical Python). % \begin{itemize} % \item % \item \href{http://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html\#numpy.linalg.svd}{docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html} for the Singular Value Decomposition, which can be used to compute the eigen values. % \end{itemize} \subsection{With \textbf{SymPy}} \href{http://docs.sympy.org/latest/modules/matrices/matrices.html\#linear-algebra}{docs.sympy.org/latest/modules/matrices/matrices.html\#linear-algebra} for linear algebra operations with the \href{http://docs.sympy.org/latest/}{SymPy} module (Symbolical Python). \paragraph{Warning:} Do not use these modules to cheat, we will see it. \textbf{You have to implement everything by yourself.} \end{document}