Resolviendo sistemas lineales de ecuaciones

Tengo un sistema de 6 ecuaciones que necesito resolver una y otra vez en un programa (con muchas entradas diferentes por supuesto). Actualmente estoy usando el método de regla de Cramer para resolver el sistema y funciona bastante bien (parece que a mi procesador le gusta mucho agregar y multiplicar operaciones, obtiene soluciones en 1 microsegundo a pesar de que las ecuaciones explícitas tienen más de 2 páginas de longitud). Sin embargo, la cantidad de veces que necesito resolver es enorme y estoy buscando un método aún más rápido.Resolviendo sistemas lineales de ecuaciones

La pregunta es, ¿existe un método aún más rápido o más eficiente para resolver estas ecuaciones o algo como CUDA sería beneficioso aquí?

Fuente

2010-07-24 Faken

¿Estás seguro de que las 6 ecuaciones son necesarias? ¿Se han reducido las ecuaciones en la medida de lo posible? – BoltBait

Estoy resolviendo un problema de estabilidad, requiere 6 DOF (3 fuerzas xyz ortogonales y 3 torques xyz). Obtuve las ecuaciones de matlab y codifiqué las soluciones explícitas en el programa (con el resultado se resolvió por separado).Sin embargo, no hay manera de que pueda simplificar las ecuaciones reales, son demasiado grandes y difíciles de manejar. – Faken

¿Cómo se calculan los determinantes? – sellibitze

tal vez usted podría dar http://arma.sourceforge.net/docs.html una oportunidad.

Proporciona la función de resolución prefabricada, http://arma.sourceforge.net/docs.html#solve. sin embargo, usa atlas/lapack backand, que está orientado más hacia funciones más grandes.

También puedes probar la multiplicación por inversión inversa, http://arma.sourceforge.net/docs.html#inv, que es una plantilla de tiempo de compilación y tal vez más rápida para tus propósitos.

prueba esto: x = inv (A) * b. Como A no cambia, la inversión se realiza solo una vez. Entonces estás en casa libre con multiplicaciones simples de matrices de vectores, que serán realmente rápidas

Fuente

2010-07-24 05:06:27 Anycorn

@GMan lo eliminó. En otra nota, estoy trabajando en cublas/ublas bridge y estoy buscando socios. ¿Conoces a alguien (o a ti mismo) que pueda estar interesado? Creo que vi un sitio que mencionas usando cuda – Anycorn

@aaa: ¿Te refieres a permitir que uBLAS de Boost (o alguna otra biblioteca BLAS) aproveche CUBLAS? Estoy interesado, per se, pero no tengo tiempo para trabajar en otra cosa. :(De hecho he usado CUDA, pero solo para hurgar, nunca he hecho nada serio con eso. – GManNickG

@GMan seguro, no hay problema. Pensé que habrías conocido a alguien. es más como tener expresiones ublas pero en GPU memoria que utiliza núcleos de cublas y pocas funciones para comunicarse: aquí está el pequeño caso de prueba: http://code.google.com/p/asadchev/source/browse/trunk/projects/boost/numeric/bindings/cublas/test.cpp – Anycorn

Puede consultar .

El método no es tan sencillo, sin embargo; querrá consultar LU decomposition.

Fuente

2010-07-24 04:29:02 GManNickG

o cualquier otra biblioteca que ofrezca cosas como descomposición de LU, sustitución hacia adelante/hacia atrás (+1) – sellibitze

¿La descomposición de LU es un método fácil de usar para resolver las cosas? Programé uno de esos algoritmos hace años en mi calculadora TI-83 mientras estaba terriblemente aburrido en la clase de métodos numéricos, como lo recordé, aunque utilizó muchas divisiones que no son muy amigables para la computadora. Voy a verlo de nuevo, tal vez pueda derivar algunas ecuaciones generales al código en el programa. – Faken

@aaa: la "forma" de mis ecuaciones es conocida y no cambia, solo los valores son diferentes (también hay ceros y unos en la matriz cuando se forman en una forma utilizable por la regla de Cramer). uBLAS no tomará eso en consideración ¿verdad? – Faken

Puede obtener al menos una duplicación utilizando SSE2 o superior. Pero eso palidecería en comparación con un puerto CUDA o OpenCL, que, de hacerse bien, podría generar una aceleración de uno o dos órdenes de magnitud.

Si conoce Python, PyCUDA podría ser un buen punto de entrada.

Fuente

2010-07-24 04:37:14

Actualmente estoy usando VS2008 en un procesador core i7, ¿SSE2 ya estaría habilitado por defecto? Si no, ¿cómo puedo habilitarlo? Además, conceptualmente, ¿cuál sería la mejor manera de implementar CUDA en un nivel muy alto (como un hilo para generar valores que se calcularán, un hilo para manejar la carga y recuperación de datos de CUDA, y uno para procesar los resultados, ect)? – Faken

Definitivamente. SSE2 se introdujo hace casi diez años. La arquitectura Core i7 es compatible con [SSE4.2] (http://en.wikipedia.org/wiki/SSE4). No puedo ayudarte en CUDA, me temo, no he jugado mucho con eso. –

La regla de Cramer no se adapta bien. Para un pequeño sistema de ecuaciones con dos o tres incógnitas está bien, pero si el sistema se hace más grande, otros métodos son más eficientes, por ejemplo: descomposición LU + sustitución directa + sustitución hacia atrás.

Fuente

2010-07-24 04:51:16 sellibitze

Sí, lo sé ... las ecuaciones son enormes. Echaré un vistazo a LU. En su opinión, ¿debería considerar el uso de una biblioteca general para resolverlos o debería limitarme a tratar de encontrar métodos más eficientes de métodos matemáticos ya que conozco detalles sobre la forma exacta del sistema de ecuaciones? – Faken

LU funciona si está resolviendo un sistema Ab = y, varias veces. La primera ejecución es costosa, las ejecuciones posteriores son rápidas. – joel3000

Si desea ejecutar CUDA, se necesita un decente tarjeta gráfica Nvidia

Si usted tiene una CPU de Intel, que Recommanded utilizar de Intel MKL http://software.intel.com/en-us/intel-mkl/, que está optimizado para Intel CPU,

Si utiliza CUDA, es posible que tenga problemas con el tema flotador o doble precisión

Además, si usted no está familiarizado con la programación de la GPU, usted va a pasar más tiempo en la solución CUDA

Fuente

2010-07-24 05:02:58 shader

Aww ... $ 400+ sí, eso está fuera de mi presupuesto operativo. Tal vez mi universidad tiene algunas licencias, pensó que descartaría poder trabajar desde casa. Soy consciente del problema simple/doble con CUDA, actualmente estoy usando el doble simplemente porque no tomo penalizaciones de velocidad debido a eso. Sin embargo, si utilizo la regla de Cramer, debería ser capaz de salirse con un solo punto debido a la falta de divisiones. – Faken

@Fake en realidad, la suma y la resta son la principal fuente de error. Multiplicación y división no tanto – Anycorn

@shader: Heh, eso es sucio ... – Faken

A menos que puedas resolver tu ecuación en orden no secuencial, CUDA no ayudará. De hecho, CUDA puede ser más lento. Cualquier cosa que no sea embarazosamente paralela no se beneficiará de CUDA. Habilitar SSE2 mediante el compilador no es suficiente. Necesita una biblioteca que esté codificada para usar SSE2. En mi opinión, la mejor biblioteca de álgebra lineal es Eigen. Es muy fácil de usar y admite SIMD (no solo SSE2).

Fuente

2010-07-26 13:47:59 user401947

¿Qué quiere decir con resolver las ecuaciones en orden no secuencial? Ahora sé que este problema es en realidad un problema de optimización de variables múltiples (aprender cosas sobre la marcha, este proyecto tiene la costumbre de hacerme eso). Sin embargo, es un problema de optimización dentro de un problema de optimización, así puedo paralelizar problemas individuales de optimización. Si obtengo la CPU principal para configurar los problemas, ¿CUDA podría ajustar los parámetros y realizar iteraciones sin que la CPU le proporcione datos de forma explícita? A diferencia de la CPU preparando una matriz y CUDA resolviéndola y simplemente devolviéndola, ¿nada más? – Faken

Piense en la GPU como un procesador multinúcleo. La GPU tiene muchos núcleos, pero cada núcleo es mucho más débil que el núcleo de la CPU. GPU tiene su fortaleza de la paralelización. ¿Puedes dividir todo el problema en subtareas que se pueden ejecutar de manera interdependiente? Digamos que tienes las ecuaciones 1, 2, ..., N. ¿Puedes resolverlas de manera independiente? Si es así, CUDA puede ayudar. Podría intentar paralelizar su código en la CPU primero, porque hacer lo mismo con CUDA es más difícil. En mi experiencia, el álgebra lineal es notoriamente difícil de paralelizar, a menos que, por supuesto, el problema consiste en subtareas independientes. – user401947

CUDA es un lenguaje de programación similar a C. La codificación de GPU implica una administración de memoria explícita. Debe tener mucho cuidado con el traslado de datos. Resolver una ecuación de 6x6 y devolver la respuesta a la CPU no justifica la sobrecarga. Para beneficiarse de GPU, su algoritmo debe ser capaz de simplificar gran cantidad de ecuaciones a la vez. No debe haber dependencia entre ecuaciones optimizadas. Entonces la GPU puede resolver todas estas ecuaciones más rápido que la CPU. – user401947

Resolviendo sistemas lineales de ecuaciones

Respuesta

Cuestiones relacionadas