%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8x,russe]{preambuleTrm}



\usepackage{iwona}


\mode<presentation>
{
  %\usetheme{Bergen}%Montpellier,Madrid}
  % or ...Frankfurt, 
  \usetheme[secheader]{Montpellier}

 % \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
  \usefonttheme{progressbar}
%  \useoutertheme{progressbar}
  %\useinnertheme{progressbar}
 % \progressbaroptions{% titlepage=normal,
  %  imagename=/home/moi/Photos/Maths/prisoner
%}
}

%\usepackage{elephantbird}
\newcommand\MyBox[2][XXX]{%
  \fbox{\tabular[b]{C{#1}} #2 \endtabular}}

\setbeamertemplate{footline}[frame number]


%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}

\ifpdf \DeclareGraphicsRule{*}{mps}{*}{} \fi
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap,shadows,patterns}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}
\hypersetup{pdfpagemode=FullScreen}

\usepackage[detect-all]{siunitx}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

\usepackage{scalefnt}
\setbeamertemplate{theorems}[numbered]

\usepackage[square]{daedale}
\bibliographystyle{cyclope}


\usepackage{algo}

\renewcommand{\algocommentfont}{\tiny\ttfamily\itshape}
\renewcommand{\algokeywordfont}{\small\ttfamily}
\renewcommand{\algotextfont}{\footnotesize\ttfamily}
\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}{/home/moi/PREPA/IPT/2014_15/Poly/}}




\setcounter{tocdepth}{2} %\setcounter{page}{0}


\newcommand{\triangleup}{\Delta}












\begin{document}


\title[]% (optional, use only with long paper titles)
{Calcul matriciel}

\subtitle{Informatique pour tou(te)s - semaines 1 \& 2}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{Lycée Clemenceau - MP / MP$^{\star}$}% (optional, but mostly needed)

\logo{\includegraphics[width=0.1\textwidth]{logoUNI}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{janvier 2016}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }



\beamerdefaultoverlayspecification{<+->}


\AtBeginSubsection[]
{\scriptsize
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\tiny
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
%\ThisCenterWallPaper{1}{logoiremBigInv}
 \Large \titlepage 
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}

\normalsize


% début
\section{Les problèmes}

\begin{frame}[fragile]
\begin{pythoncode}
sage: a = matrix(4,[10,7,8,7,7,5,6,5,8,6,10,9,7,5,9,10])
sage: a
[10  7  8  7]
[ 7  5  6  5]
[ 8  6 10  9]
[ 7  5  9 10]
sage: b = matrix(4,1,[32,23,33,31])
sage: b
[32]
[23]
[33]
[31]
sage: bb = matrix(4,1,[32.1,22.9,33.1,30.9])
sage: bb
[32.1000000000000]
[22.9000000000000]
[33.1000000000000]
[30.9000000000000]
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
sage: X = a.solve_right(b)
sage: X
[1]
[1]
[1]
[1]
\end{pythoncode}

\pause

\begin{pythoncode}
sage: X = a.solve_right(bb)
sage: X
[  46/5]
[ -63/5]
[   9/2]
[-11/10]
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
sage: a = matrix(4,[0,0,0,1e-4,1,0,0,0,0,1,0,0,0,0,1,0])

sage: a.eigenvalues()
[0.100000000000000, -0.100000000000000, -0.100000000000000*I, 0.100000000000000*I]

sage: a = matrix(4,[0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0])
sage: a.eigenvalues()
[0, 0, 0, 0]  
\end{pythoncode}
\end{frame}



\begin{frame}
  Conditionnement: ${\rm cond} A = \Vert A \Vert × \Vert A^{-1}\Vert$

\pause 
$\|AB\| \le \|A\|\|B\| $

\pause

Plus c'est petit (proche de 1), plus c'est stable.


\pause

Difficile à savoir.




\end{frame}



\begin{frame}[fragile]
  Système de Cramer: $n^2×n!$ opérations élémentaires...

\pause

$\approx 5×10^{141}$ siècles pour un système  $100×100$ avec mon processeur i5 de
60 GFLOPs...

\pause

\begin{pythoncode}
sage: factorial(100)*10^4/(60*10^9*3600*24*365.25*100)
4.92888218389781e141  
\end{pythoncode}


\end{frame}






\section{Pivot de Gau\ss}

\begin{frame}
  Vous connaissez...

\pause
\begin{multicols}{2}
$$A=
\begin{pmatrix}
  ε&-1&1\\
  -1&2&-1\\
  2&-1&0
\end{pmatrix}
$$

$$
B=
\begin{pmatrix}
  0\\0\\1
\end{pmatrix}
$$
\end{multicols}
\pause
\vspace{1cm}

On cherche $X$ telle que $AX=B$
\end{frame}


\section{NUMPY}



\begin{frame}[fragile]\frametitle{numpy}
  \begin{pythoncode}
    import numpy as np
  \end{pythoncode}
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
a = np.array([[1,2,3],[4,5,6]])

b = (np.array(np.arange(1,7))).reshape(2,3)

c = np.matrix([[1,2,3],[4,5,6]])

d = np.matrix('1 2 3; 4 5 6')
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [29]: a*a
Out[29]: 
array([[ 1,  4,  9],
       [16, 25, 36]])
\end{pythoncode}

\pause

\begin{pythoncode}
In [30]: a.dot(a)
---------------------------------------------------------------------------

ValueError: shapes (2,3) and (2,3) not aligned: 3 (dim 1) != 2 (dim 0)  
\end{pythoncode}

\pause

\begin{pythoncode}
In [31]: c*c
---------------------------------------------------------------------------

ValueError: shapes (2,3) and (2,3) not aligned: 3 (dim 1) != 2 (dim 0)  
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [32]: c * c.transpose()
Out[32]: 
matrix([[14, 32],
        [32, 77]])
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [33]: np.eye(4,4)
Out[33]: 
array([[ 1.,  0.,  0.,  0.],
       [ 0.,  1.,  0.,  0.],
       [ 0.,  0.,  1.,  0.],
       [ 0.,  0.,  0.,  1.]])
\end{pythoncode}

\pause

\begin{pythoncode}
In [34]: np.eye(4,4, dtype=bool)
Out[34]: 
array([[ True, False, False, False],
       [False,  True, False, False],
       [False, False,  True, False],
       [False, False, False,  True]], dtype=bool)  
\end{pythoncode}
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [42]: a = np.zeros((2,3), dtype=int)

In [43]: a
Out[43]: 
array([[0, 0, 0],
       [0, 0, 0]])
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [47]: np.diag(np.arange(5))
Out[47]: 
array([[0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 2, 0, 0],
       [0, 0, 0, 3, 0],
       [0, 0, 0, 0, 4]])
\end{pythoncode}

\pause


\begin{pythoncode}
In [49]: a > 0
Out[49]: 
array([[False, False, False, False, False],
       [False,  True, False, False, False],
       [False, False,  True, False, False],
       [False, False, False,  True, False],
       [False, False, False, False,  True]], dtype=bool)  
\end{pythoncode}


\end{frame}






\begin{frame}[fragile]
\begin{pythoncode}
In [51]: a = np.random.rand(3,3)

In [52]: a
Out[52]: 
array([[ 0.08468479,  0.01769339,  0.89631521],
       [ 0.90388521,  0.71191769,  0.60721673],
       [ 0.16991842,  0.26063882,  0.08871752]])
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [53]: np.linalg.det(a)
Out[53]: 0.095088125094619114
\end{pythoncode}

\pause

\begin{pythoncode}
In [54]: np.linalg.inv(a)
Out[54]: 
array([[-1.00017403,  2.44031334, -6.597658  ],
       [ 0.24174255, -1.52266579,  7.97937737],
       [ 1.20540439, -0.2005057 ,  0.46583953]])  
\end{pythoncode}

\pause

\begin{pythoncode}
In [55]: a.dot(np.linalg.inv(a))
Out[55]: 
array([[  1.00000000e+00,   0.00000000e+00,   1.11022302e-16],
       [  0.00000000e+00,   1.00000000e+00,   2.77555756e-16],
       [  4.16333634e-17,  -1.45716772e-16,   1.00000000e+00]])  
\end{pythoncode}




\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
In [64]: b = np.random.rand(3,1)
In [65]: x = np.linalg.solve(a,b)  
\end{pythoncode}


\pause

\begin{pythoncode}
In [68]: a.dot(x) == b
Out[68]: 
array([[False],
       [False],
       [False]], dtype=bool)
\end{pythoncode}

\pause

\begin{pythoncode}
In [69]: np.array_equal(a.dot(x), b)
Out[69]: False
\end{pythoncode}

\pause

\begin{pythoncode}
In [70]: np.allclose(a.dot(x), b)
Out[70]: True
\end{pythoncode}
\end{frame}

\section{Gau\ss: le retour}


\begin{frame}[fragile]

  \begin{center}
    Choix du pivot maximum
  \end{center}

\pause

\begin{pythoncode}
def trouve_pivot(A,dep) :
    ind_max = dep
    for k in range(dep + 1, len(A)) :
        if abs(A[k,dep]) > abs(A[ind_max,dep]) :
            ind_max = k
    return ind_max
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]

\begin{center}
Transvection: $L_i ← L_i + k×L_j$
\end{center}

\pause

\begin{pythoncode}
def transvection(A,i,j,k) :
    A[i] += k * A[j]
\end{pythoncode}
\end{frame}




\begin{frame}[fragile]


  \begin{center}
    Échange $L_i ↔ L_j$
  \end{center}

\pause

\begin{pythoncode}
def echange(A,i,j) :
    tmp = copy(A[i])
    A[i], A[j] = A[j], tmp
\end{pythoncode}
\end{frame}






\begin{frame}[fragile]
\begin{pythoncode}
def gauss(A,B) :
    T = np.concatenate((A,B), axis = 1)
\end{pythoncode}
\pause
\begin{pythoncode}
    ind_max = len(A)
    assert ind_max == len(A[0]), "Matrice non carrée" 
\end{pythoncode}
\pause
\begin{pythoncode}
   for row_piv in range(ind_max) :
        ligne_piv = trouve_pivot(T, row_piv)
        if ligne_piv > row_piv :
            echange(T, row_piv, ligne_piv)
\end{pythoncode}
\pause
\begin{pythoncode}
        pivot = T[row_piv, row_piv]
        for sub_row in range(row_piv + 1, ind_max):
            coeff = T[sub_row, row_piv] / pivot
            transvection(T, sub_row, row_piv, -coeff)
\end{pythoncode}


\end{frame}


\begin{frame}[fragile]


Le tableau est maintenant triangulaire. Il ne reste plus qu'à effectuer la phase
de remontée.

\pause

\begin{pythoncode}
    Sol = np.arange(ind_max, dtype=np.float)
    for i in range(ind_max - 1, -1, -1):
        Sol[i] = (T[i, ind_max] - sum(T[i,j]*Sol[j] for j in range(i+1, ind_max))) / T[i,i]
    return Sol  
\end{pythoncode}





\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
In [24]: a = np.random.rand(1000,1000)

In [25]: b = np.random.rand(1000,1)
\end{pythoncode}
\pause
\begin{pythoncode}
In [26]: %timeit gauss(a,b)
1 loops, best of 3: 3.27 s per loop  
\end{pythoncode}
\pause
\begin{pythoncode}
In [27]: %timeit np.linalg.solve(a,b)
1 loops, best of 3: 421 ms per loop  
\end{pythoncode}
\end{frame}









\begin{frame}[fragile]
  \begin{exercice}
    \begin{enumerate}
    \item Comment  modifier  la  fonction   \verb+gauss+  pour  calculer  le
déterminant d'une matrice?
\item pour calculer l'inverse d'une matrice?
    \end{enumerate}
  \end{exercice}
\end{frame}


\section{Complexité}

\begin{frame}[fragile]
\begin{pythoncode}
def trouve_pivot(A,dep) :
    ind_max = dep
    for k in range(dep + 1, len(A)) :
        if abs(A[k,dep]) > abs(A[ind_max,dep]) :
            ind_max = k
    return ind_max
\end{pythoncode}

\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def transvection(A,i,j,k) :
    A[i] += k * A[j]
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def echange(A,i,j) :
    tmp = copy(A[i])
    A[i], A[j] = A[j], tmp
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def gauss(A,B) :
    T = np.concatenate((A,B), axis = 1)
    ind_max = len(A)
    assert ind_max == len(A[0]), "Matrice non carrée"
    for row_piv in range(ind_max) :
        ligne_piv = trouve_pivot(T,row_piv)
        if ligne_piv > row_piv :
            echange(T, row_piv, ligne_piv)
        pivot = T[row_piv, row_piv]
        for sub_row in range(row_piv + 1, ind_max):
            coeff = T[sub_row, row_piv] / pivot
            transvection(T, sub_row, row_piv, -coeff)
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
Sol = np.arange(ind_max, dtype=np.float)
    for i in range(ind_max-1, -1, -1):
        Sol[i] = (T[i,ind_max] - sum(T[i,j]*Sol[j] for j in range(i+1, ind_max))) / T[i,i]
    return Sol
\end{pythoncode}
\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
In [87]: %timeit gauss(a,b)
10 loops, best of 3: 21.9 ms per loop

In [88]: a = np.random.rand(200,200)

In [89]: b = np.random.rand(200,1)

In [90]: %timeit gauss(a,b)
10 loops, best of 3: 93.8 ms per loop
\end{pythoncode}

\pause

??????????????????????
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
In [79]: a = np.random.rand(100,100)

In [80]: %timeit transvection(a,1,10,3)
100000 loops, best of 3: 3.27 µs per loop

In [81]: a = np.random.rand(200,200)

In [82]: %timeit transvection(a,1,10,3)
100000 loops, best of 3: 3.67 µs per loop

In [83]: a = np.random.rand(400,400)

In [84]: %timeit transvection(a,1,10,3)
100000 loops, best of 3: 3.81 µs per loop
\end{pythoncode}
\end{frame}


\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
