Multiplicacion Rapida De Matrices

´ INSTITUTO POLITECNICO NACIONAL Escuela Superior de F´ ısica y Matem´ticas a

Multiplicaci´n R´pida de Matrices o a
Tesis que presenta

Yanira Pachuca Herrera∗
Para obtener el Titulo de Licenciado en F´ ısica y Matem´ticas a

Director de Tesis

Dr. Adri´n Alc´ntar Torres∗ a a

M´xico, D. F. e
∗

13 de diciembre de 2008

Participante en los proyectos CONACyT 49251-F, SIP-IPN20071670 y 20082743

Agradecimientos
En primer lugar, dedico este trabajo a mi Padre y Hermano Pedro Pachuca P´rez, e a mi Madre y amiga Margarita Herrera Alem´n, por su Amor a lo largo de toda mi vida. a Agradezco a Claudia Pachuca Herrera y a Miguel Angel Riezco Lagunes, por el apoyo al inicio de este trabajo. Al Dr. Adri´n Alc´ntar Torres, por haberme ofrecido el tema de esta tesis y por su aa paciencia durante el desarrollo de la misma. A mis Profesores y Amigos: Antonio de Gante Ugarte, Emigdio Salazar Cordero, Pablo Lam Estrada, Abelardo Santaella Quintas, Guillermo Arreguin S´nchez, y a mi a querida amiga Guillermina Regalado. A la E.S.F.M y al I.P.N.

ii

CAP´ ITULO 0. AGRADECIMIENTOS

Prefacio
La multiplicaci´n de matrices es una operaci´n muy com´ n en ciencias eingenier´ o o u ıa, sin embargo, su costo computacional es elevado; por lo que es necesario disponer de alternativas para la ejecuci´n de esta tarea de manera eficiente disminuyendo el tiempo o de procesamiento. El estudio de este trabajo es dar a conocer uno de los algoritmos que resuelve el problema de multiplicar matrices de dimensiones grandes, donde principalmente, se busca reducir el tiempo dec´mputo empleado. Para lograr este objetivo se o decid´ dividir este trabajo en los siguientes cap´ ıo ıtulos: 1. En el cap´ ıtulo 1 Recordaremos la definici´n de Matriz, la definici´n de un proo o ducto de matrices, as´ como sus propiedades y concluiremos con un ejemplo que ı nos permita convencernos sobre el hecho de que asociando adecuadamente las matrices a la hora de intentar calcular un productode matrices, reduce el n´ meu ro de operaciones que se requiere para efectuar dicho producto, trayendo como consecuencia un ahorro de tiempo para obtener la respuesta. 2. Dedicaremos el cap´ ıtulo 2 al estudio de la funci´n generatriz. Comenzaremos o con algunos ejemplos muy sencillos los cuales nos permitir´n formarnos una idea a sobre esta valiosis´ ıma herramienta, despu´s presentaremos sudefinici´n formal y e o finalmente la emplearemos para resolver algunos problemas. ´ 3. Comenzaremos el cap´ ıtulo 3 con la definici´n de Arbol, veremos paso a paso como o se construyen y como estos objetos nos permitir´n calcular el n´ mero de formas a u distintas en que se se puede parentizar un producto de matrices, y as´ poder ı concluir como al aumentar el n´ mero de matrices en un producto, el n´ merode u u parentizaciones distintas crece dram´ticamente. a 4. Estudiaremos en el cap´ ıtulo 4 la Notaci´n Asint´tica, veremos su aplicaci´n como o o o herramienta para medir la eficiencia de un algoritmo. Despu´s enunciaremos el e Teorema Maestro el cual es uno de los teoremas principales en el An´lisis de a Algoritmos y veremos mediante algunos ejemplos la forma tan contundente de saber de maneraexacta la complejidad de un algoritmo al aplicar este teorema. 5. El cap´ ıtulo 5 es considerado de gran importancia, ya que en el explicaremos a detalle el concepto de Programaci´n din´mica y la forma en que emplearemos o a este m´todo para resolver el problema de multiplicar una cadena de matrices e encontrando la parentizaci´n ´ptima. Al final del cap´ o o ıtulo se presenta el c´digo o delprograma dise˜ ado en base a las ideas centrales de la Programaci´n din´mica n o a

iv

CAP´ ITULO 0. PREFACIO el cual al ser implementado en un computador devuelve la parentizaci´n ´ptima o o y el producto ya calculado. 6. Aqu´ veremos y analizaremos el Algoritmo de Strassen y lo aplicaremos a un ı ejemplo sencillo el cual nos permitir´ deducir que este algoritmo solo conviene a para calcular...