Ingeniero Civil en Computación / Dado un tetraedro, o pirámide de base triangular, es posible bisectarlo por el plano formado por el punto medio de una arista y los vértices opuestos a la misma lo que produce dos nuevos tetraedros. Si se aplica esto desde el punto medio de una de las aristas más largas se conoce como bisección por la arista más larga . Existe interés en estudiar las propiedades matemáticas de los tetraedros obtenidos por la bisección iterativa tetraedros por su arista más larga. El tema de memoria propuesto consiste en el desarrollo de una herramienta computacional para estudiar la bisección iterativa de tetraedros por su arista más larga. Para esto se construye una estructura de datos en forma de árbol en que cada nodo hijo almacene los tetraedros semejantes y distintos que se obtienen al aplicar dicha bisección sobre el tetraedro de su nodo padre. En esencia esta memoria consta de tres partes: (1) El desarrollo de un sistema que soporta realizar operaciones sobre tetraedros utilizando computación exacta; (2) La implementación de la bisección por la arista más larga sobre tetraedros; (3) La construcción de una estructura de datos que soporte la aplicación iterativa de esta técnica sobre los tetraedros resultantes. El trabajo y la herramienta computacional se utilizarán para apoyar el estudio teórico sobre el comportamiento de la bisección iterativa de tetraedros, y para desarrollar nuevas técnicas de triangulación con propósitos aplicados.

Doctor en Ciencias, Mención Computación / La generación y refinamiento de mallas son temas de gran interés en aplicaciones tales como simulación de fenómenos físicos mediante el uso de los métodos de elementos finitos, en aplicaciones CAD, modelado geométrico y mallas geométricas. Una malla es un conjunto de elementos geométricos (polígonos o poliedros) que no se superponen, los cuales están conectados por medio de vértices, aristas y caras, que se usan para aproximar dominios geométricos. Los algoritmos de refinamiento producen mallas cada vez más finas para discretizar dominios complejos, representar objetos con topologías arbitrarias y también superficies con formas complejas. En esta tesis se estudió la paralelización de algoritmos de refinamiento basados en el concepto de Lepp para sistemas multicore (multinúcleo) y sistemas distribuidos. Se consideraron dos problemas: (1) refinamiento de mallas de buena calidad: aquí dada una malla de entrada de buena calidad, ésta es iterativa y localmente refinada (de acuerdo a un requerimiento externo a la aplicación) para producir una malla final de calidad análoga a la inicial; (2) refinamiento de triangulaciones Delaunay de mala calidad, donde dada una triangulación Delaunay de entrada de mala calidad (con una geometría dada), deseamos producir una triangulación Delaunay de buena calidad y de tamaño óptimo. Algoritmos basados en el concepto de Lepp son algoritmos refinamiento por la arista más larga mejorados donde el refinamiento de cualquier triángulo t tiene asociado un Lepp(t). En el contexto de los sistemas multicore se desarrollaron algoritmos Lepp-bisección multicore eficientes y escalables para el refinamiento de mallas de 2 y 3 dimensiones. También se desarrolló un algoritmo Lepp-Delaunay multicore para la generación de mallas Delaunay de buena calidad. En el contexto de los sistemas de memoria distribuida se desarrolló un algoritmo Lepp-bisección distribuido para el refinamiento de mallas de 2 dimensiones donde la malla inicial es subdividida dentro de un conjunto de submallas (o subparticiones), las cuales son distribuidas entre los procesadores. También se desarrolló una estrategia eficiente para garantizar que se obtiene una malla final válida (conforme) en las interfaces de submallas vecinas. Se realizaron evaluaciones empíricas de los algoritmos paralelos sobre arquitecturas multicore y sistemas de memoria distribuida que muestran que los algoritmos paralelos tienen buen desempeño.