|
|
|
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.
|
|
|
