Reducción del efecto fill-in en sistemas lineales sparse de matriz simétrica

• Autores: José Ramón Franco Brañas
• Directores de la Tesis: Pedro Ramón Almeida Benítez (dir. tes.)
• Lectura: En la Universidad de Las Palmas de Gran Canaria ( España ) en 1996
• Idioma: español
• Tribunal Calificador de la Tesis: Francisco Rubio Royo (presid.) , Gustavo Montero García (secret.) , Nacere Hayek Calil (voc.) , Gabriel Winter Althaus (voc.) , Agustín de la Villa Cuenca (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • DADO UN SISTEMA DE ECUACIONES LINEALES AX=B, DE MATRIZ A SPARSE, PUEDE OCURRIR QUE EN EL TRANSCURSO DE LA FACTORIZACION DE LA MATRIZ A MUCHAS ENTRADAS NULAS DEJEN DE SERLO, A ESTE HECHO SE LE CONOCE CON EL NOMBRE DE EFECTO FILL-IN. SE DEBE PROCURAR QUE DICHO EFECTO SEA PEQUEÑO PARA REDUCIR COSTES DE ALMACENAMIENTO, ERRORES DE REDONDEO Y TIEMPO DE EJECUCION.

    EL OBJETO DE ESTA TESIS, ES HACER UN ANALISIS DE DICHO EFECTO, UTILIZANDO LA ESTRUCTURACION MEDIANTE GRAFOS ASOCIADOS A LAS MATRICES DE LOS SISTEMAS. INVESTIGAMOS LOS METODOS ONE-WAY Y NESTED DISSECTION PARA RESOLVER PROBLEMAS QUE SE PRESENTAN EN APLICACIONES DE ELEMENTOS FINITOS, OBSERVANDO QUE LA RENUMERACION INTERNA DE LOS BLOQUES EN EL ALGORITMO ONE-WAY (UTILIZANDO EL ALGORITMO DE GRADO MINIMO) REDUCE EL EFECTO FILL-IN, ASI COMO LA DISTANCIA ENTRE SEPARADORES AUMENTA DICHO EFECTO. POR OTRA PARTE, HEMOS OBSERVADO QUE DICHO ALGORITMO DE GRADO MINIMO NO ES ADECUADO PARA MALLAS REGULARES (OPERADOR LAPLACIANO DE 5 PUNTOS) DESDE EL PUNTO DE VISTA DE REDUCCION DEL EFECTO FILL-IN, DEL MISMO MODO QUE EL DE CUTHILL-MCKEE NO LO ES PARA MALLAS CON OPERADOR DE 9 PUNTOS. ADEMAS, HEMOS DESARROLLADO UN NUEVO ALGORITMO, DENOMINADO GO-AWAY, QUE AL APLICARLO A MALLAS REGULARES (OPERADOR DE 5 PUNTOS) REDUCE DICHO EFECTO AL COMPARARLO CON OTROS ALGORITMOS.

    POR ULTIMO, SEÑALAMOS VARIAS CUESTIONES QUE CONSTITUYEN VIAS FUTURAS DE INVESTIGACION, RELACIONADAS CON LOS TOPICOS TRATADOS EN ESTA TESIS, TALES COMO LA ESTRATEGIA A SEGUIR EN EL TIE-BREAKING EN EL ALGORITMO ONE-WAY, LA ELECCION DE LOS SEPARADORES EN DICHO ALGORITMO, EL REORDENAMIENTO CON LOS ALGORITMOS ONE-WAY Y GO-AWAY EN METODOS ITERATIVOS, LA ADAPTACION DE SUBRUTINAS A ORDENADORES EN PARALELO O VECTORIALES, ETC.