Revista de la Universidad Cristóbal Colón
Número 19 (Edición digital)

 

Algoritmo MPI para crear un fractal en el conjunto Mandelbrot

Jesús Antonio Álvarez Cedillo *

Resumen
Parecería como si el arte y la ciencia se combinaran en el conjunto de Mandelbrot. Es tal su complejidad, su belleza y su colorido que se ha convertido en el modelo más estudiado en análisis del caos y la dinámica de los sistemas no lineales; cualquier persona que lo vea, aun sin tener ningún tipo de conocimiento científico, encuentra una extraña belleza en su interior y en su figura característica. Aunque una computadora personal puede realizar los cálculos necesarios para generar este fractal, los cuales son numerosos y complejos, el procesamiento paralelo permite realizarlo con más calidad en la imagen y a mayor velocidad, al distribuir los procesos en múltiples procesadores. El MPI, como lenguaje estándar de programación para máquinas paralelas, representa un entorno ideal para el desarrollo de proyectos científicos que involucran los procesos de recursividad.


Para citar este artículo puede utilizar el siguiente formato:

Álvarez Cedillo, J.A.: Algoritmo MPI para crear un fractal en el conjunto Mandelbrot en Revista de la Universidad Cristóbal Colón Número 19, edición digital a texto completo en www.eumed.net/rev/rucc/19/


El texto contenido en esta página web puede estar incompleto y carecer de notas a pie de página, imágenes, gráficos o fórmulas. Su objetivo es facilitar al investigador que lo encuentre en los buscadores de Internet y que pueda revisarlo.
Puede bajarse el artículo completo (11 páginas, 221 Kb) en formato PDF comprimido ZIP pulsando aquí.




1. INTRODUCCIÓN

Se define como fractal a aquellos objetos cuya creación depende de las reglas de irregularidad o de fragmentación al ser estudiadas por un proceso matemático, es definida también como un objeto matemático de dimensión no entera.

Según B. Mandelbrot [1], se considera fractal al objeto o estructura que consta de fragmentos con orientación y tamaño variable, pero de aspecto similar. Esta característica le proporciona al
fractal algunas propiedades geométricas especiales que dependen de su longitud y la relación entre el área de su superficie y su volumen.

Estas propiedades especiales hacen que se requieran otras herramientas matemáticas diferentes a las comunes para poder explicar sus características. En el cuerpo humano existen estructuras con geometría fractal, como son la red vascular, las ramificaciones bronquiales, la red neuronal, la disposición de las glándulas, etc.
 

La importancia que tiene esta geometría fractal en el organismo es que permite optimizar la función de los sistemas debido a que en el mínimo espacio tienen la máxima superficie. Al existir estructuras con geometría fractal deducimos que deben ser posibles los fenómenos con características fractales, al poder poseer estos fenómenos, unos patrones que se repiten constantemente en diferentes escalas de tiempo. Es importante mencionar que cumple con las reglas de paralelización al tener la característica antes mencionada.

Estos fenómenos son analizados, por lo general, con el uso de herramientas matemáticas de la geometría fractal. De acuerdo con H. P. Koch [2], la teoría fractal puede ser considerada como una herramienta válida y útil para el estudio de fenómenos dinámicos en el cuerpo humano o en la naturaleza y nos permite una aproximación más acorde con la complejidad y la ausencia de linealidad existente en dichos procesos.

La programación MPI, como una herramienta en la actualidad, es novedosa; el uso de clusters ha permitido al súper cómputo ingresar a la teoría del caos. Los algoritmos actuales que trabajan en sistemas de un solo procesador no están preparados para soportar miles e incluso millones de iteraciones.

El presente algoritmo pretende ser un avance significativo en la materia de procesamiento paralelo que permita ayudar en el estudio de los fractales usando MPI.

1.2. Aplicaciones de los fractales
Aunque puedan parecer simples figuras creadas para uso y entretenimiento de los matemáticos, existen muchas aplicaciones de los fractales tanto a nivel teórico como práctico. Considerando la gran variedad de áreas de estudio científico y su gran importancia es imposible hacer una lista de aplicaciones, por lo que consideré para este trabajo sólo las más importantes. Su aplicación en el campo de las ciencias abstractas ha sido
realmente grande y una de sus aplicaciones, en donde se ha comportado como una innovación, es el estudio en los sistemas de ecuaciones de segundo grado, aunque se han hecho consideraciones donde los fractales son utilizados para resolver ecuaciones.

El matemático John Hubbard presentó un trabajo utilizando el método de Newton [3], para resolver ecuaciones. Para realizar esto evaluó, desde diferentes puntos iniciales, cada una de las soluciones. Usando su computadora para realizar la exploración y asignando un color a cada cuenca, Hubbard comprobó que los límites de estas regiones del plano no estaban bien definidos. En estos límites se encontraron puntos de un color dentro de otros puntos de color y conforme la rejilla de números, y se iba ampliando a medida que más compleja se iba revelando la frontera. En realidad, podía considerarse que no existía tal frontera.

Generalmente, las aplicaciones más comunes son generadas por la física o la sismología, pero el campo donde más aplicaciones se han encontrado ha sido el del tratamiento de las imágenes.

Michael Barnsley fue el pionero en el tratamiento de imágenes a partir de su denominada transformación fractal [4]. Ésta consiste en el proceso contrario a la formación de un fractal, es decir, en lugar de crear una figura a partir de unas reglas determinadas, se buscan las reglas que forman una figura más determinada. Los fractales se utilizan para comprimir imágenes digitalizadas, de forma que ocupen menos espacio y puedan ser transmitidas a una mayor velocidad y con menores recursos de cómputo. En la industria del cine es de gran utilidad a la hora de crear los espectaculares efectos especiales de las grandes producciones, ya que es fácil crear todo tipo de paisajes y fondos a través de los fractales. Se observa en la figura 1, un fractal generado con MPI, en un cluster de alto rendimiento que simula un árbol.
158
En el mundo de la música, los fractales juegan un papel muy importante en la composición, en especial, de música tecno o de bases rítmicas para cualquier otro tipo de música. En el mundo de la biología se pueden apreciar grandes ejemplos de estructuras fractales en el cuerpo humano, como la red de venas y arterias.

A partir de un vaso sanguíneo grande como la aorta van saliendo vasos más pequeños hasta la aparición de los finísimos capilares, de forma que cubran el mayor espacio posible para llevar nutrientes a las células. Por otro, se cree adivinar cierta similitud entre la generación de fractales y el código genético, ya que en ambos casos, a partir de una información muy reducida en apariencia, surgen complejas estructuras.
Figura 1. Simulación de un árbol utilizando un fractal.
2. MARCO TEÓRICO
2.1 Fractales y caos
La dimensión fractal es un índice matemático que es posible calcular y que nos permite cuantificar las características de los objetos o fenómenos fractales. Este índice puede calcularse de varias formas. Por lo general es utilizado un modelo matemático llamado el exponente de Hurst [5].

La concepción de dimensión que nosotros usamos normalmente en la euclidiana clásica, es aquella en la que una dimensión es una recta, dos
dimensiones forman un plano y tres dimensiones forman un objeto con volumen. A estas coordenadas les llamamos el eje X o largo, el eje Y o alto y el eje Z, profundidad o espesor (como se presenta en la figura 2).
Figura 2. Representación de una dimensión en la euclidiana clásica.

La geometría fractal y los descubrimientos de la ciencia del caos se basan en los números complejos. A diferencia del resto de los números, los números complejos no existen sobre la recta numérica en lo absoluto, ni siquiera en aproximación, como en el caso de los números reales. Los números complejos sólo existen en un plano de x-y que involucra a los llamados números imaginarios. Tienen únicamente una referencia indirecta con la recta numérica.

2.2 Los números complejos
Los números complejos [6] son una combinación de números imaginarios que no tienen lugar físico sobre la recta numérica, y de cualquier otro tipo de número que sí tenga un lugar definido sobre la recta numérica. En las matemáticas, los números complejos se representan mediante una letra z, la cual define al número complejo como:

z= a + bi
Donde:
a y b = número real
I= número imaginario
159
Tanto la parte real como la imaginaria del número complejo pueden ser positivas o negativas, y cualquiera de los dos puede ser entero o fraccional. Los números complejos pueden fácilmente sumarse, restarse, multiplicarse o dividirse. El uso de x y y proporciona una referencia al plano cartesiano, lo cual ayuda al mejor entendimiento de los números complejos.

El eje x es la representación de la recta numérica que se coloca en forma horizontal, mientras que el eje y representa la línea de los números imaginarios, de raíces cuadradas negativas. El eje y se muestra verticalmente para crear un plano de números complejos.

como z= x + yi x= número real
yi= número imaginario

Todo número no-complejo tiene un lugar sobre la unidimensional recta numérica, mientras que todo número complejo tiene un lugar sobre el plano más amplio de dos dimensiones de los números, que se denomina como el plano complejo. De manera que para localizar un número complejo hay que referirse al eje horizontal para ubicar su parte numérica real y al eje vertical para ubicar su parte numérica imaginaria. Esto contrasta con todos los números que pueden localizarse en un punto que se encuentra sobre una línea recta unidimensional.

La representación de un número en el plano complejo, por ejemplo Z=2-3i, es presentado en la figura 3.

Si ahora consideramos que existe una línea irregular, ésta tiende a formar una superficie, y si se dobla se convierte en un volumen; se trata de una técnica muy general de convertir un objeto plano en un objeto con tres dimensiones.

Muchas estructuras naturales tienen las características de los fractales; por lo que, geométricamente, estas estructuras podrían tener
una dimensión no entera entre dos y tres dimensiones.
Figura 3. Representación de 2 -3i sobre el plano complejo.
La dimensión fractal es un índice que nos permite analizar mejor las características geométricas de los objetos usando la geometría fractal. Los fenómenos con comportamiento fractal pueden ser representados por medio de gráficos de líneas, y en estos gráficos se mide su dimensión fractal y, de esta forma, el análisis de la complejidad de su dinámica caótica. Es posible considerar que la relación más importante entre el caos y los fractales está en que los fractales son la representación gráfica del caos.

La relación existente entre el caos y los fractales es posible ya que los fractales son figuras geométricas con un cierto patrón que se repite infinitamente y a múltiples escalas; si las imágenes son observadas detenidamente se podrá descubrir que en ese patrón se encontrarán los mismos componentes hasta el infinito. Esto lo podemos verificar si observamos el fractal a diversas escalas cada vez más pequeñas. Un fractal sin dimensión entera representa la forma gráfica en la solución de las ecuaciones caóticas.

De manera simple, entonces es posible definir un fractal como una figura geométrica con una estructura muy compleja y pormenorizada a cualquier escala, la cual tiene las siguientes características:
 

1.Los fractales son figuras geométricas, aunque no se ajusten y sea imposible su definición por medio de los conceptos y métodos clásicos vigentes desde Euclides.
2. Se originan a partir de unas situaciones iniciales o reglas muy básicas, que darán lugar a figuras extremadamente complejas.
3. La autosemejanza. Es definida como la simetría existente dentro de una escala; esta característica los vuelve recurrentes y paralelizables.

3. ANÁLISIS DEL ALGORITMO Y SU SOLUCIÓN PARALELA
compuesto por una parte real y otra imaginaria representada por i, donde:
Representado de la siguiente forma: 2 + 3i.
Entonces, tomamos un número cualquiera C y lo elevamos al cuadrado. Al número obtenido le sumamos C y lo volvemos a elevar al cuadrado y continuamos una y otra vez con el mismo proceso: Esto genera la siguiente ecuación:
z
2
Es decir x n =(x n- 1 ) 2 - (y nJ+a
y n = 2 x n - 1 y n - 1 + b
Si después de realizar la gráfica, el punto Z n se encuentra a una distancia menor que 2 unidades del origen, entonces el punto P(a,b) pertenece al conjunto de Mandelbrot. En la práctica puede resultar complicado realizar un número muy grande de iteraciones, de forma que se debe evaluar el conjunto de Mandelbrot por aproximaciones; existen dos aspectos de este proceso que se deben saber: cuándo se encuentra el punto dentro del conjunto o cuándo no lo está.

A continuación veremos dos fases de este proceso, donde se analizará el funcionamiento correcto del algoritmo, se le darán valores y se solucionará la ecuación:
a. El punto puede escapar al infinito alejándose del centro del plano y no pertenece al fractal de Mandelbrot.

Veamos cómo se comporta un punto con un color particular dentro del plano; empezaremos con un punto fuera del conjunto del Mandelbrot:
C = -0.5 + i
Iteracionando la función Z n = Z n-1 2 + C produce los siguientes valores:
Número Valor actual Distancia de
de paso origen
1 -0.5 +i 1.12
2 -1.25 1.25
3 1.06 + I 1.46
4 -0.37 + I * 3.1 3.15
La gráfica resultante de las iteraciones obtenidas se presenta en la figura 5.

En la tercera iteración se aprecia que la distancia del punto de origen es más grande de dos. Esto nos indica que el punto C no se mantiene dentro del conjunto del Mandelbrot.
Figura 5. Gráfica que muestra el comportamiento de un punto fuera del Mandelbrot.
b. El número obtenido y el punto de encuadre se encuentran dentro del fractal.
Si se hace el mismo procedimiento con un punto dentro del conjunto del Mandelbrot C = 0.2 + i * 0.5, en este caso, la distancia del punto de origen nunca será mayor a dos. Cuando se alcanza el número máximo de iteraciones, por ejemplo 200, es asumido que el punto inicial C se encuentra dentro del conjunto Mandelbrot y es pintado en negro.
Número Valor actual Distancia de
de paso origen
1 0.2 + i * 0.5 0.54
2 -0.01 + i * 0.7 0.7
3 -0.29 + I * 0.49 0.57
4 0.05 + I * 0.22 0.22
5 0.15 + i * 0.52 0.54
6 -0.05 + i * 0.66 0.66
7 -0.23 + i * 0.44 0.48
8 0.06 + i * 0.3 0.3
.. ....................... .......................

La gráfica resultante de las iteraciones obtenidas se presenta en la figura 6.
162
Figura 6. Gráfica que muestra el comportamiento de un punto fuera del conjunto de Mandelbrot.
La función equivalente en lenguaje C sería la siguiente:
void compute(double x, double y, double c_real, double c_imag,
double *ans_x, double *ans_y)
{
*ans_x = x*x - y*y + c_real; *ans_y = 2*x*y + c_imag;
}
Como puede observarse en la función llamada compute en el programa, La función se definió para que soporte un proceso recursivo.

4. RESULTADOS

Un problema que se presentó en el desarrollo del proyecto fue la manera de poder almacenar el resultado en un archivo gráfico; es importante reconocer que el entorno de programación MPI contiene aún, un limitado entorno gráfico y aunque existe el entorno MPE, no sería posible guardarlo en un archivo.

Investigando la manera de generar este archivo, se encontró la forma de crear archivos PGM (Portable Greyscale Images, por sus siglas en inglés), ya que es un formato simple bajo el inconveniente de que genera archivos en escalas de grises.

Para esto se le agregó al algoritmo la siguiente librería: pgm.h.
La función pgmWriterHeader es utilizada con la
declaración de una variable de tipo archivo (FILE), que genera la cabecera de lectura, y la función converttoworld convierte cada dato calculado en píxeles que son escritos a continuación de la cabecera.

Las funciones descritas son las siguientes:
a. Función de creación de cabecera:
void pgmWriteHeader (FILE *f, int width, int height, int maxval )
{
fprintf (f, "P5\n%d %d\n%d\n", width, height, maxval );
}
b. Función de escritura de datos:
void convertToWorld (int ix, int iy, int imgsize, double xmin, double xmax,
double ymin, double ymax, double *xw, double
*yw)
{
double x, y;
x = ix;
y = imgsize - iy;
x /= imgsize; // normaliza
y /= imgsize;
x = ( x * (xmax-xmin) + xmin );
y = ( y * (ymax-ymin) + ymin ); *xw = x;
*yw = y;
}
Como resultado de este análisis se deriva el siguiente programa:
#include <stdio.h>
#include <math.h> #include <sys/time.h> #include "mpi.h”
Se incluye una función que calcule la distancia entre x y el eje y:
163
double distance(double x, double y)
{
return(x*x + y*y);
}
Por último, se hace la integración de mpi sobre la ecuación, de donde se tiene el siguiente programa:
/* Autor: M.C. Jesús Antonio Álvarez Cedillo CIDETEC-IPN
Dibujo de un Mandelbrot usando comandos MPI y MPE
*/
void compute(double x, double y, double c_real, double c_imag,
double *ans_x, double *ans_y)
{
*ans_x = x*x - y*y + c_real; *ans_y = 2*x*y + c_imag;
}
double distance(double x, double y) {
/* calcula la distancia entre x y el eje y. * Recibe: doubles x y el eje y.
* Regresa x^2 + y^2.
*/
return(x*x + y*y);
}

/* salida de la cabecera del archivo PGM*/
void pgmWriteHeader ( FILE *f, int width, int height, int maxval )
{
fprintf ( f, "P5\n%d %d\n%d\n", width,
height, maxval );
}

void convertToWorld ( int ix, int iy, int imgsize, double xmin, double xmax,
Double ymin, double ymax, double *xw, double *yw )
{
double x, y;
x = ix;
y = imgsize - iy;
x /= imgsize; // normaliza
y /= imgsize;

X = ( x * (xmax-xmin) + xmin ); y = ( y * (ymax-ymin) + ymin );

*xw = x; *yw = y;
}

/* Programa principal

int main(int argc, char* argv[]) {
const int IMAGE_SIZE = 1024; const int MAX_ITER = 255; int n, ix, iy;
double r_min, r_max; double i_min, i_max; double x,
y,
c_real,
c_imag;
MPI_Init(&argc,&argv);
/* Ingreso
printf("\nIngresa el rango sobre la exis REAL (ej, -2,2): ");
scanf ("%lf,%lf", &r_min, &r_max ); printf("\n Ingresa el rango sobre la exis IMAGINARIO(ej, -2,2):");
scanf ("%lf,%lf", &i_min, &i_max );
FILE *f = fopen ( "mandel.pgm", "w" ); pgmWriteHeader ( f, IMAGE_SIZE, IMAGE_SIZE, 255 );

for (iy = 0; iy < IMAGE_SIZE; iy++) {
for (ix = 0; ix < IMAGE_SIZE; ix++)
*/
164
convertToWorld ( ix, iy, IMAGE_SIZE, r_min, r_max, i_min, i_max,
&c_real, &c_imag );
x = y = 0.0;
n = 0;
while (n < MAX_ITER && distance(x,y) < 4.0)
{
compute(x,y,c_real,c_imag,&x,&y); n++;
}
if (n < MAX_ITER )
fputc ( n%2?255:100 , f ); else
fputc ( 0, f );
}
}
fclose ( f ); MPI_Finalize();
}
El algoritmo trabajó muy bien para diferentes rangos de evaluación del conjunto de Mandelbrot, a una velocidad muy aceptable y con resultados estupendos. Un ejemplo de esto se muestra en la figura 7, donde se genera un fractal en el rango de x real (-0.25,-0.125) y en el rango de x imaginario (-0.125,-0.62). Como puede observarse, se debe ingresar un rango de valores en los reales y en los imaginarios para que, en relación con estos valores, se puedan realizar las iteraciones.
Figura 7. Fractal de prueba generado por el algoritmo.

El anterior programa deberá compilarse utilizando C estándar en cualquier sistema que
soporte el compilador MPICH, usando la orden mpicc y es posible hacerlo funcionar utilizando hasta 256 procesadores, con la orden mpirun.

4. CONCLUSIONES

La construcción de un algoritmo paralelo ya es una tarea compleja que involucra la manera en que los datos deberán ser manejados, el uso de las iteraciones y el desempeño óptimo que mejore la velocidad de procesamiento. Por otro lado, la cuarta dimensión es el hogar de los números complejos y de la geometría fractal. Se trata del continuo espacio-temporal del hombre y la naturaleza, en donde existe un constante cambio basado en la retroalimentación. Como lo descubrió Mandelbrot, la cuarta dimensión incluye no sólo a las tres primeras dimensiones, sino también a los intervalos existentes entre ellas, las dimensiones fractales.

La fórmula de Mandelbrot es un resumen de sus descubrimientos en la geometría fractal de la naturaleza [1], en el mundo real de la cuarta dimensión. Esto contrasta con el mundo idealizado de las formas euclidianas de las dimensiones primera, segunda y tercera. Estas formas habían preocupado a la casi totalidad de los matemáticos anteriores a Mandelbrot. La geometría euclidiana estaba relacionada con una perfección abstracta que es prácticamente inexistente en la naturaleza. Ésta era incapaz de describir la forma de una nube, de una montaña, de una playa o de un árbol. El uso de nuevos algoritmos que utilicen MPI para resolver problemas de fractales proporcionan al investigador nuevas herramientas de referencia.
En su libro “The Fractal Geometry of Nature” (La
geometría fractal de la naturaleza), Mandelbrot menciona [1]: “Las nubes no son esferas, las montañas no son conos, las playas no son círculos, y los ladridos no son agradables, ni la luz viaja en línea recta.”

A tal comentario anexo: “Nada en este mundo es lo que aparenta ser”.
 


FUENTES DE CONSULTA

MANDELBROT, B. The Fractal Geometry of Nature, Freeman and Co. 1977.

PRUSINKIEWICZ, P.; SANDNESS, G.: "Koch Curves as Attractors and Repellers", IEEE Computer, 1988.

H U B B A R D A N D S C H L E I C H E R A N D SUTHERLAND, How to Find All Roots of Complex Polynomials by Newton's Meted, INVMATH: Inventiones Mathematical, 2001

MICHAEL BARNSLEY, Fractals Everywhere, Academic Press Inc., second edition 1993. BRIGGS, J. PEAT, F. D. Turbulent Mirror. Harper & Row Pub. USA. 1989.

DONAL L. TURCOTTE, Fractals and Chaos in Geology and Geophysics, Cambridge University Press, 1992.

TITU ANDREESCU, DORIN ANDRICA, Complex Numbers from A to Z, Birkh~user Boston; 1 edition, July 2005.

K E N N E T H F A L C O N E R , M a t h e m a t i c a l Foundations and Applications, John Wiley & Sons; 2nd edition, 2003.
 


* Maestro en ciencias de la informática egresado de UPIICSA IPN, docente e investigador del Centro de Innovación y Desarrollo Tecnológico en Cómputo del Instituto Politécnico Nacional, responsable del laboratorio de procesamiento paralelo. Correos
electrónicos: antoin.alvarez@laposte.net , jesusantonioa@cidetec.ipn.mx Tel. (01)55 56242000 Ext. 42015.
 


Nota Importante a Leer:

Los comentarios al artículo son responsabilidad exclusiva del remitente.

Si necesita algún tipo de información referente al artículo póngase en contacto con el email suministrado por el autor del artículo al principio del mismo.

Un comentario no es más que un simple medio para comunicar su opinión a futuros lectores.

El autor del artículo no está obligado a responder o leer comentarios referentes al artículo.

Al escribir un comentario, debe tener en cuenta que recibirá notificaciones cada vez que alguien escriba un nuevo comentario en este artículo.

Eumed.net se reserva el derecho de eliminar aquellos comentarios que tengan lenguaje inadecuado o agresivo.

Si usted considera que algún comentario de esta página es inadecuado o agresivo, por favor, pulse aquí.

Comentarios sobre este artículo:

No hay ningún comentario para este artículo.

Si lo desea, puede completar este formulario y dejarnos su opinion sobre el artículo. No olvide introducir un email valido para activar su comentario.
(*) Ingresar el texto mostrado en la imagen



(*) Datos obligatorios

 


Editor:
Juan Carlos M. Coll (CV)
ISSN: 1988-5245
EUMEDNET

Inicio
Acerca de ...
Números anteriores
Anuncios y Convocatorias
Otras Revistas de EUMEDNET
Universidad de Málaga > Eumed.net > Revistas > RUCC