Resumen de Métodos computacionales para problemas de grandes dimensiones

David Santo Orcero

• El estudio de sistemas de grandes dimensiones siempre ha supuesto un problema de tratamiento complejo. Es la denominada por Richard E. Bellman maldicion de la dimensionalidad; o tambien conocida por efecto Hughes. Este efecto se re ere a que segun aumentamos las dimensiones a un espacio matematico, aumenta exponencialmente su volumen asociado.

  Esto supone una di cultad importante para numerosos problemas que se modelan va espacios multidimensionales, ya que ante el incremento lineal del problema que se pre- tende solucionar, el calculo de la solucion supone incrementos exponenciales en el tiempo de computo y la necesidad de almacenamiento intermedio; suponiendo que numerosos proble- mas, siendo resolubles en teora, no pueden ser resueltos en la practica.

  Actualmente la algoritmia para resolver muchos problemas esta muy avanzada; pero cuando el numero de dimensiones aumenta, la capacidad que tenemos de resolver estos prob- lemas disminuye. Esto supone que no nos bastara con tener apenas un algoritmo generico para resolver una familia de problemas; sino que tendremos que estudiar en profundidad cada problema para intentar encontrar patrones que permitan su resolucion con los recursos computacionales de los que dispone la humanidad en la actualidad.

  Para nuestro trabajo hemos escogido dos problemas distintos: el calculo del estado fun- damental de agregados moleculares, que supone en la practica la diagonalizacion de matrices inmensas en un proceso de optimizacion que requerira miles de millones de iteraciones; y las ecuaciones en derivadas parciales, que suponen la multiplicacion de matrices de unas dimensiones cuyas dimensiones son la el cubo de la resolucion de mayado; las necesidades de almacenamiento la cuarta potencia de la resolucion de mayado, y el tiempo de computo la quinta potencia de la resolucion del mayado.

  Para el primer caso, hemos propuesto dos tecnicas; una primera para resolver la operacion computacional mas costosa del proceso de diagonalizacion mediante un algoritmo que no destruye la esparsidad {el algoritmo de Lanczos-, y otra para identi car buenas propuestas de partida en el proceso de optimizacion para el calculo de con guraciones de mnima energa.

  Para el segundo, hemos propuesto una forma de calculo del algoritmo voraz de actualizaciones de rango uno.

  1