Algoritmo Gauss-Jordan paralelo

Todo cuanto tiene que ver con la obtención, almacenamiento y proceso de la información digital, sus aplicaciones y el software y hardware utilizado.
Mensaje
Autor
Avatar de Usuario
Homer
Mensajes: 2151
Registrado: Dom Abr 30, 2006 2:07 pm
País: España
Ciudad: Sabadell
Contactar:

Algoritmo Gauss-Jordan paralelo

#1 Mensaje por Homer »

¡Ojo que este examen es para nota! Se trata de resolver un sistema de n ecuaciones lineales con n incógnitas. Pero tienen que hacerlo x alumnos (el “grupo GPU” ) sobre la pizarra, repartiéndose el trabajo para terminar antes que el empollón de la clase (el “joputa CPU”) que trabaja solo. Cada uno de los x alumnos hará sus anotaciones y cálculos particulares pero compartiendo la pizarra, que es lo que va a misa.

Aquí hay un ejemplo: http://repositorio.uigv.edu.pe/bitstrea ... sAllowed=y pero no vale copiar, porque lo he comprobado y el “joputa CPU” va como 15 veces más rápido.

No hay plazo para resolverlo, pero para compensar tampoco hay premio.

Avatar de Usuario
baldo
Mensajes: 1514
Registrado: Vie Dic 23, 2005 7:54 pm
País: españa
Ciudad: coruña y madrid
Ubicación: Galicia
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#2 Mensaje por baldo »

¿quieres resolver una matriz enorme?.
¿o es peque y la quieres resolver rapido?.
¿o quieres calcular su inversa?.

* para el resto de lectores: me carteo con homer para discutir algunas ideas, que no publico por poder ser patentables,,,

lo que si puedo comentar es un problemilla que me tope hace poco, al jugar con matrices enormes, de 1000x1000,
a poco que sean los coeficientes y/o las variables, tras unas 1000 multiplicaciones, desborda el limite de los doubles del ordenador, unos 1e250

Avatar de Usuario
Homer
Mensajes: 2151
Registrado: Dom Abr 30, 2006 2:07 pm
País: España
Ciudad: Sabadell
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#3 Mensaje por Homer »

Estoy utilizando este método: https://es.wikipedia.org/wiki/Eliminaci ... uss-Jordan que me parece el más intuitivo y rápido. Intuitivo es porque lo entiendo hasta yo.

Codificarlo en c es sencillo:

Código: Seleccionar todo

void GaussJordan(float* A, int rango) {
    int rangox = rango + 1;
    for (int z = 0; z < rango; z++) {
        float a = B(z, z);
        for (int x = z; x < rangox; x++) B(x, z) /= a;  //primer elemento no nulo = 1
        for (int y = z + 1; y < rango; y++) {
            a = B(z, y);
            for (int x = z; x < rangox; x++) B(x, y) -= B(x, z) * a;  //columna abajo = 0
        }
    }
    for (int z = rango - 1; z > 0; z--) {
        float a = B(rango, z);
        for (int i = z - 1; i >= 0; i--) {      //Columna arriba = 0
            B(rango, i) -= a * B(z, i);
            //B(z, i) = 0;                        //Innecesario
        }
    }
}
Resuelve 1000 ecuaciones en 0,8 segundos, pero hay tres bucles for anidados así que el tiempo de cálculo crece con la tercera potencia del rango. Yo lo que quiero es resolver 100.000 ecuaciones y vivir para verlo.

Avatar de Usuario
baldo
Mensajes: 1514
Registrado: Vie Dic 23, 2005 7:54 pm
País: españa
Ciudad: coruña y madrid
Ubicación: Galicia
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#4 Mensaje por baldo »

me repite la pregunta.
tienes 1k ecuaciones, entiendo que con 1k incognitas, y que entras con 1k variables.
osea, una matriz 1k x 1k , y quieres resolverla,

DIAGONARLA NO VALE DE NADA, porque EDITADO: tienes que hacer un tratamiento previo de las variables (pasarlas por una matriz), Y posterior en la incognitas despejadas.

en una granja hay A cabezas, y B patitas. calcula conejos y pollitos.
tu pretendes una diagonal, que entrando con cabezas de te conejos,,,

el rollito de las matrices, no es mas que una escritura taquigrafica de los sistemas de ecuaciones de toda la vida,
el GJ es la clasica resolucion por ¿"reducion"?, y si, funciona, es facil, pero despues tienes que rehacer los nudos que desiciste,,,

Avatar de Usuario
Homer
Mensajes: 2151
Registrado: Dom Abr 30, 2006 2:07 pm
País: España
Ciudad: Sabadell
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#5 Mensaje por Homer »

Un ejemplo:

A11*X + A12*Y + A13*Z = B1
A21*X + A22*Y + A23*Z = B2
A31*X + A32*Y + A33*Z = B3

Estas 3 ecuaciones con 3 incógnitas las convierto en una matriz “ampliada”:

A11 A12 A13 B1
A21 A22 A23 B2
A31 A32 A33 B3

Y aplicando el algoritmo de marras me queda en esto:

1 0 0 C1
0 1 0 C2
0 0 1 C3

Con el resultado de cada incógnita en la columna rango+1:

X = C1
Y = C2
Z = C3

Rápido e indoloro: 1.000 ecuaciones en 0,8 segundos.

Pero si quiero calcular 100.000 ecuaciones me llevaría 9,26 días, a menos que disponga de una GPU con 1024 poderosos núcleos, que me lo resolvería en 13 minutos. Este es el asunto.

Avatar de Usuario
baldo
Mensajes: 1514
Registrado: Vie Dic 23, 2005 7:54 pm
País: españa
Ciudad: coruña y madrid
Ubicación: Galicia
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#6 Mensaje por baldo »

¿Con que entras, y con que sales?,
Si entras con XYZ, estas son las variables, B1,2,3 son las incognitas.
si es al reves, necesitas la inversa de la matriz.

resolver una matriz, por grande que sea, siempre sera mas rapido que calcular su GJ.

olvidas que C1,2,3 es un cristo de la hostia que involucra a todos los Bs, multiplicados por unos coeficientes relacionados con los As

9 dias dices,,,???, cuanto te va llevar salir del GJ?

oye,,, y pa que quieres tu una 100k x100k?

Avatar de Usuario
Homer
Mensajes: 2151
Registrado: Dom Abr 30, 2006 2:07 pm
País: España
Ciudad: Sabadell
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#7 Mensaje por Homer »

En float* A entra la matriz ampliada, en chorro: A11, A12, A13, B1, A21, A22, A23, B2, A31, A32, A33, B3. Y cuando termina tengo los resultados en las mismas posiciones donde metí B1, B2 y B3. ¡Pero ojo! si inicialmente A11 = 0 hay que intercambiar la primera fila por otra, o se va todo al carajo. No lo programé porque en mi caso nunca se da esa circunstancia.

Por cierto, el método más sencillo para calcular la inversa de una matriz es precisamente este mismo, el de Gauss-Jordan, sustituyendo la columna B1, B2, B3 por una matriz unitaria del mismo rango: {{1,0,0}, {010}, {001}}. Al final te queda a la derecha la matriz inversa y a la izquierda la matriz unitaria. Lo explica aquí también: https://es.wikipedia.org/wiki/Eliminaci ... uss-Jordan

Tienes razón, llevo bastante más de nueve días con esta mierda :lol:


Es para el simulador. Sé los potenciales de cada una de las superficies conductoras, pero no sé la distribución de cargas. Divido la superficie en miles puntos, y calculo la distribución. Si tiene que pasar una partícula por un orificio de un milímetro y tengo las cargas separadas por milímetros… sale por los cerros de Úbeda.

Avatar de Usuario
baldo
Mensajes: 1514
Registrado: Vie Dic 23, 2005 7:54 pm
País: españa
Ciudad: coruña y madrid
Ubicación: Galicia
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#8 Mensaje por baldo »

vaya choque de trenes, yo me creo en la seguridad de tener razon,,,
ante la duda miro tu link a wiki,
y ciertamente, en el ejemplo, 8,-11,-3 son las variables, y XYZ las incognitas,
lo que hacen es el clasico metodo de reducion. ¿o tu como las despejarias?.
esto esta muy bien, pero solo te vale para ese caso especifico, el de 8,-11,-3
pero si quieres preparar la maquina para otras variables, con los mismos coefis, tienes que irte a una inversa.
inversa que puede calcularse como dices.

Avatar de Usuario
Homer
Mensajes: 2151
Registrado: Dom Abr 30, 2006 2:07 pm
País: España
Ciudad: Sabadell
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#9 Mensaje por Homer »

Perdona bonito pero ha sido un choque del AVE contra una fragoneta de malacatones :lol:

Te juro que el algoritmo que he puesto funciona perfectamente y no utiliza la inversa para nada. Yo no conocía este método, a mi me enseñaron la regla de Cramer (se ve que no le bajó hasta resolverlo). Pero el tiempo crece con el factorial del rango, así que es inviable.

Bueno, superado el escollo vamos al meollo, me da igual el algoritmo ¿cómo paralelizo?

En el documento que he puesto al principio: http://repositorio.uigv.edu.pe/bitstrea ... sAllowed=y en el Kernel3 (apartado 5.3), donde dice “AB[j] =AB[j]/piv ;” todos los procesos están intentando simultáneamente modificar la misma fila, lo cual es un conflicto que lo ralentiza todo. Lo he corregido pero sigue funcionando como el culo, así que hay algo aun peor. No lo puedo entender ¿nadie lo ha comprobado?

Avatar de Usuario
Homer
Mensajes: 2151
Registrado: Dom Abr 30, 2006 2:07 pm
País: España
Ciudad: Sabadell
Contactar:

Re: Algoritmo Gauss-Jordan paralelo

#10 Mensaje por Homer »

Bueno, cayó pieza, ya no pierdo más el tiempo con el puñetero documento. Hay tres bucles anidados, uno en Kernel1, otro en Algoritmo1, y un tercero oculto: a menos que disponga de una GPU con 10.000 núcleos es imposible que se ejecuten 10.000 kernel1 simultáneamente. Se ejecutan por grupos sucesivamente, ahí está el tercer bucle. Por tanto el tiempo aumenta con la tercera potencia del rango, exactamente igual que en la CPU. Según dice aquí: https://www.geektopia.es/es/product/nvi ... ce-gt-520/ solo dispone de 48 núcleos, no 10.000, así que se trata de una más de ese lamentable 66% de publicaciones científicas fraudulentas.

Responder

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 5 invitados