Determinante de matriz nxn

[GabrielBAP]

Olá pessoal.

Estou tentando desenvolver um programa para calcular o determinante de uma matriz nxn. Pesquisei na internet e encontrei alguns métodos de achar esse valor. O método que estou usando no arquivo anexado é um método genérico para encontrar o determinante de qualquer matriz nxn, porém sempre que testo o programa e comparo o valor usando o MATLAB, o valor encontrado só é correto quando a matriz entrada é 1x1, 2x2 ou 3x3. Acima disso é retornado um valor diferente.

Não consegui descobrir o motivo do problema, alguém tem uma ideia de como corrigir esse erro?

Obrigado.

[Vinicius Jarina]

Eu tentaria utilizar a fórmula de Laplace, talvez seja computacionamente mais caro, mas acho que é mais simples de implementar, e com certeza mais divertido =)

2012/7/6 GabrielBAP <gabri...@gmail.com>

--
Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] Colabore com a Pesquisa de Preferência de Conteúdo
para Eventos do Grupo C & C++ Brasil:
http://www.surveymonkey.com/s/GBBGTXN
------~----~-------~---~---~---~---~----------------~------------~---------~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en

[Matheus Lima]

Tente implementar a eliminação de Gauss-Jordan.

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] Colabore com a Pesquisa de Preferência de Conteúdo
para Eventos do Grupo C & C++ Brasil:
http://www.surveymonkey.com/s/GBBGTXN
------~----~-------~---~---~---~---~----------------~------------~---------~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en

--
Matheus Lima
LDS - Laboratório de Desenvolvimento de Software - IFCE

Graduando em Engenharia de Teleinformática - UFC

[E. Tadeu]

http://bit.ly/PqdpPi

  :D

[]'s

2012/7/6 Matheus Lima <matheus...@gmail.com>

[Уθя¡ςκ]

SymbolicC++ possui uma implementação de um algoritmo de cálculo de determinantes, e creio que funciona no caso genérico. Eu não sei que algoritmo é, na época que vi essa lib há alguns anos achei é muito interessante por ser mínima e depender somente da STL e não cair pra otimização em assembly, então resolvi dar uma olhada pra ver como ela implementa o cálculo de determinante e é realmente o código minúsculo mas muito eficiente se for comparar com o que eu iria fazer via uma implementação inocente da fórmula de Laplace ou da eliminação Gauss-Jordan. Na época não consegui encontra uma referência pra que algoritmo é esse que esta nessa lib e deixei queto, mas recomendo dar uma olhada.

[Walter Mascarenhas]

 

Dois pontos:

 

1) A primeira questâo a se pensar quando se deseja

calcular um determinante é:  para que? Na maioria

das vezes calcular um determinante nâo é a melhor forma

de se resover um problema

 

2) Laplace é uma péssima idéia. Tem complexidade

exponencial. Ou seja só funciona para matrizes

muito pequenas.

 

3) Computação simbólica só deve ser usada em

casos extremos, quando nâo dá para fazer

a coisa numéricamente. Há situações que ela

é essencial, mas em geral este não é o caso.

 

4) Gauss Jordan, ou eliminação de Gauss

com pivoteamento parcial ou completo´

sâo métodos robustos e eficientes.

Eles me parecem a melhor opção

para o caso geral.

 

          walter.

[Уθя¡ςκ]

On Saturday, July 7, 2012 9:19:25 AM UTC-3, Walter Mascarenhas wrote:

 

3) Computação simbólica só deve ser usada em

casos extremos, quando nâo dá para fazer

a coisa numéricamente. Há situações que ela

é essencial, mas em geral este não é o caso.

SymbolicC++ possui classes auxiliares além do núcleo de computação simbólica, por exemplo a classe VeryLong, para aritmética de precisão arbitrária. A classe de matriz é uma delas.

[Walter Mascarenhas]

 

Eu nâo conhecia o Symbolic C++ e parece

bem bacana mesmo.

Eu sou mais familiar com o GNU GMP.

 

  Ainda assim, na minha opinião, o uso

deste tipo de ferramenta só é

justificado em casos específicos.

 

Por exemplo, há situações em geometria

computacional nas quais aritmética de

precisão arbitrária é

a melhor (e talvez única) opção.

 

  Porém, em geral, é melhor usar um algoritmo

estável e robusto em aritmética de ponto

flutante mesmo. Você terá uma boa

aproximação do determinante em

uma fração do tempo (e memória)

do que obteria em precisão arbitrária.

 

Uma análise ingênua da eliminação

gaussian sugere que para representar

exatamente o determinante de uma

matrix n x n com entradas com b bits

você precisará (nos casos genéricos)

de pelo menos 2^n x b bits, É muito

bit para n grande.

 

  Seria interessante ver como o

symbolic C++ se sai ao calcular

o determinante de uma matriz 100x100

com entradas aletórias de 32bits, por

exemplo. Se alguem fizer isto e

mostrar que a minha teoria do

parágrafo anterior está errada eu

agradeço.

 

  Finalmente, uma curiosidade:

calcular o permante, que é

uma versão do determinante sem

os sinais de menos, é um exemplo

clássico de problema extremamente

difícil em teoria da computação; A análise

dele foi um dos ingredientes que levaram

a medalha Turing (premio top em computação)

para Leslie Valiant.

 

Quem gosta deste tipo de coisa deve ler

 

http://rjlipton.wordpress.com/2011/03/22/valiants-permanent-contributions/

 

 

               walter.

[Уθя¡ςκ]

On Saturday, July 7, 2012 3:03:40 PM UTC-3, Walter Mascarenhas wrote:

 

  Ainda assim, na minha opinião, o uso

deste tipo de ferramenta só é

justificado em casos específicos.

 

Por exemplo, há situações em geometria

computacional nas quais aritmética de

precisão arbitrária é

a melhor (e talvez única) opção.

 

  Porém, em geral, é melhor usar um algoritmo

estável e robusto em aritmética de ponto

flutante mesmo. Você terá uma boa

aproximação do determinante em

uma fração do tempo (e memória)

do que obteria em precisão arbitrária.

A classe de matriz é genérica, o VeryLong é só um tipo auxiliar de brinde. 

[Walter Mascarenhas]

 

Y*******,

 

    Ou seja, é um template que você pode instanciar com

T = double e chamar matrix.det() ou algo assim?  Se for está ótimo.

 

  Uma correção: O Arnaldo Mandel, um amigo que pensa

com mais calma que eu, me alertou que na verdade o

determinamente de uma matrix n x n com entradas de b

bits pode ser representado com O( n b + n log (n) ) bits.

 

  O cenário castrófico de 2^n bits só ocorreria nos

passos intermediários de um algoritmo descuidado

(como uma implementação ingênua de eliminação

guassiana usando aritmética racional)

 

   Por isso ainda mais curioso em saber como

o symbolic C++ se sairia ao calcular o determinante

de matrizes n x n com n grande.

 

   Tem como voce testar isso (eu teria muito

trabalho...)

 

                    walter.

[Уθя¡ςκ]

On Saturday, July 7, 2012 5:43:49 PM UTC-3, Walter Mascarenhas wrote:

   Tem como voce testar isso (eu teria muito

trabalho...)

Pra mim foi divertido: https://gist.github.com/3073073 

[Уθя¡ςκ]

Alterando o clang pra usar libc++ e pondo -O3 deu uma melhorada. Atualizei a gist.

[Walter Mascarenhas]

 

 Y*,

 

   Obrigado por testar. qualitativamente era

algo assim que eu esperava (só não sabia

bem o tamanho da diferença):

 

   O tempo com veryLong é umas duzentas

vezes maior que com double para dimensao

20 ou 30. (Corrigindo pela diferença de

tamanho de 20 para 30, isto levaria

a um fator de umas 700 vezes)

 

   Já que vocë veio até aqui (já tem o código

pronto etc) seria legal fazer mais dois testes:

 

1) Ver como a diferença de tempo escala

com o tamanho da matriz

 

2) Ver como é o erro no determinante

calculado com double e long (se ele nâo

"promover"  long para veryLong)

Teria que ver o erro relativo (det<double> - det<veryLong>) / det<veryLong>

(O absoluto vai ser enorme...)

 

  Dei mais uma sapeada na internet e os

bounds teóricos para o tempo dos

algoritmos exatos sao melhores do que eu pensava.

(assim como o fator de 700 acima está abaixo

do que eu esperava)

 

Se voce procurar os artigos de um tal de

 Kaltofen no google verá que, grosso modo e

sem exagerar nos detalhes, há algoritmos

em aritmética exata que calculam determinantes

de matrizes n x n com b bits em tempo da

ordem de n^3 b.  

 

  n^3 é tempo de cálculo da eliminação gaussiana

com float/double. Portanto **EM TEORIA** a diferença

de tempo estarã só na constante em frente ao n^3,

que no seu example está na casa dos 700,

 

  Para mim a conversa também está divertica,

[Уθя¡ςκ]

A lib é genérica, ou seja, compilação de dll, é só pegar o .h e include e blza, dá uma olhada no determinant.cpp, eu vo tomar meu banho =D

[Rodrigo Madera]

2012/7/8 Уθя¡ςκ <obl...@gmail.com>

eu vo tomar meu banho =D

Verdade... hoje é Domingo.

;-)

[Marcos de Lima Carlos]

Gauss-Jordan nesse caso é o mais simples de ser implementado mas é computacionalmente caro.
http://www.youtube.com/watch?v=ZuaIjvBPTBc

O video acima está em espanhol. Vale a pena dar uma lida e tentar entender como funciona.

[]s

--
Marcos de Lima Carlos
CEO - Sir and Sir
http://blog.sirandsir.com

O trabalho em equipe permite que você ponha a culpa no outro.

[Walter Mascarenhas]

Y*,

  Baixei o código e dei uma olhada no método dele

para calcular o determinante

.

   Me parece bem ruinzinho. Ele usa uma identidade

esperta para obter o determinante. Porém, 

1) Em aritmética de ponto flutuante (double e float)

o método é ordem n^4 e me parece instável

(os erros de arredondamento crescem demais)

Eliminação Guassiana é 1/3 n^3 e, com

pivoteamento, se comporta razoavelmente bem

em termos de arredondamento.

2) Em aritmética exata, tenho a impressão que

o método leva a um número exponencial

(2^n) bits nos cálculos intermediários. Porém,

não posso afirmar isto com certeza pois

algum argumento esperto poderia mostra

que estou errado. 

3) Na prática, os tempos são desastrosos.

   Por estas e outras, me parece que é uma

má idéia usar o symbolic c++ para calcular

determinantes.

   Se voce realmente quer calcular os

determinantes exatamente então é

melhor olhar os artigos dos especialistas,

como o Kaltofen,

  Na prática eu ficaria mesmo com a eliminação

de gauss com pivoteamento parcial, como disse

no início desta conversa.

   walter.

[Walter Mascarenhas]

Y*,

  Para deixar evidente que usar o Symbolic C++ é

uma má idéia: Tome uma matriz<int64_t> 7x7 com as

duas primeiras linhas com todas entradas iguais

a 1000 e nas demais linhas coloque 0 fora da diagonal

e 1000 na diagonal. 

   Esta matriz tem determinante 0 (duas linhas iguais)

Segundo o symbolic c++ o determinante é 818089675.

Se voce fizer com int32_t verá que já dá errado para

uma matriz 4x4 parecida com acima: as duas primeiras

linhas iguais a 1000 e terceira e quarta como

na identidade.

  Agora  entendo perfeitamente o código do symbolic++ 

e sei que ele usa um número linear de bits. Assim, para

calcular o determinante de uma matriz com entradas

de tamanho 1000 (10 bits) ele precisara de 7 x10 = 70bits

e isto da mais que um int64_t. No caso 4x4 

ele precisará de 40 bits e já dá overflow em int32_t

 Ou seja, mesmo para a pergunta ingenua inicial, no começo

desta thread, o symbolic c++ é uma má resposta.

          walter.

[Уθя¡ςκ]

dá um desconto vai:

[ 922517755 2071460592  33284580  1068187840  69737960  1707306105  17215521 ]

[1578452749 1189861052  626980100 2099768518 1210710875 1010120800 1242056065]

[1695235615 1159436556  383583814  147253604  990161084  786558185 1921568010]

[1934460484 1722422655  678001025  614996193  402222740 2026554071 1203629877]

[ 111387999 1639842656  30393794  1874871419  936386702 1091135298 1348091753]

[1425616821  866860968  803227928  769580854  51407297   714014585  304510659]

[ 457115012 1183001365 1300337629 1980938731 1198272476  263862566  184415707]

Determinant of the 7x7 matrix (with MAX_RAND maximum input) is -5420368547496656379536554144048065783192794930531190434790327970

The calculation time took 995 ms

Basta bater o olho no algoritmo do determinante que fica fazendo trace da diagonal desde o inicio pra ver que a sua configuração vai dar pau com tipos básicos. Mas é um algoritmo pequeno o suficiente pra servir de introdução de forma didática, e o Verylong e o Rational<> estão lá pra ajudar quando já der pra notar uso de tipos básicos falhando.

Por ser uma lib header only, com hearders auto-contidos, tem um certo valor mesmo não usando o melhor dos melhores algoritmos.

[Walter Mascarenhas]

    Dou todos os descontos, e falo com todo bom humor. 

Na verdade acabei aprendendo com esta história e está

bem divertido e instrutivo. 

    Dentro deste espírito de cordialidade e de aprender

junto, tenho que dizer o seguinte:

1) O que mata no algoritmo dele não é o trace, mas sim 

o produto *this * B. Isto custa n^3 operações envolvendo

(k + 1) b bits por operação no passo k (b bits em *this) 

e k b bits por entrada de B. No frigir dos ovos isso

leva a um algoritmo O(n^5 b) enquanto os algoritmos

tops fazem O(n^3 b). A diferença de n^2 é signficativa.

2) Se ele usasse o GNU GMP poderia fazer as operações

mais rápido que o very long dele. Note que GMP, é livre e muito bem feito. 

Me parece que seria melhor fazer VeryLong e Rational como c++ wrapper do

GMP.(mas você tem razão ao dizer que ai não seria auto contido)

3) O ponto de usar double ao invés de long é justamente poder

lidar com as matrizes que você exibe na sua última mensagem

Isto também é um aprendizado importante: quando usar

double. Claro que double também explode (dá overflow por volta

de 10^300 ) mas dá uma quilometragem bem maior antes do

desastre invevitavel.

  É isso, me desculpe se pareci não dar desconto algum.

O objetivo é aprender e falar livremente (sem medo de

dizer besteira) é parte importante do processo. 

                walter.

[Otávio Basso Gomes]

Olá, 

O livro Métodos Numéricos Aplicados mostra o calculo de determinante usando a fatoração LU, através do algoritmo de Crout, que é uma variação de: http://en.wikipedia.org/wiki/Doolittle_decomposition

Otávio

2012/7/6 GabrielBAP <gabri...@gmail.com>

--

[Bruno Gouvêa]

Eis um exemplo de uma implementação em Python3 para cálculo de determinantes de matrizes nxn que é relativamente rápido:

http://ideone.com/6UAbsd

Acredito estar correto, porém fica díficil de conferir valores de matrizes muitos grandes...

O que acham?

Bruno.

[Matheus Lima]

Bruno Gouvêa, não faça por Laplace nunca. Esse algorítmo é podre para ser implementado computacionalmente. Faça por Gauss Jordan.

Eu implementei o Gauss-Jordan em C, se quiser dá uma olhada para comparar com tua imlementação em python.

https://github.com/matheuslima/algebralinear

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~

[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 

--

Matheus Lima

[Bruno Gouvêa]

Matheus Lima, na verdade eu não usei somente Laplace, se vc olhar o código eu usei ele aliado a um "pseudo" Gauss Jordan...

Não uso inversões nem nada, apenas tento zerar a maior quantidade de colunas abaixo da diagonal principal pra que o laplace não tenha que fazer recursões excessivas..  isso pareceu ter um bom resultado...

Dei uma olhada na sua implementação, mas não consegui entender direito o que voce fez...

Mas em relação ao tempo de execução, por exemplo para uma matriz 100x100, qual o tempo seu código leva em média pra calcular o determinante?? Só pra eu ter uma base se o custo computacional do meu código está muito alto comparado a uma implementação em C.

Valew!

Abraço.

[Matheus Lima]

Cara, eu havia esquecido que meu código somente invertia uma matriz usando Gauss-Jordan, mas eu adicionei um método para calcular o determinante por Gauss-Jordan. O procedimento consiste em criar uma matriz triangular superior a partir da matriz original. O determinante da matriz original é dado pelo produto dos elementos da diagonal principal da matriz triangular. Olha meu github novamente, eu adicionei um arquivo matrix.dat com uma matriz 100 x 100 gerada pelo octave.

Como são feitas muitas multiplicações com ponto flutuante, há um pequeno erro em meu algorítmo. Enquanto que com o octave o determinante da matriz em questão é igual a -395 no meu código ele é igual a -396, mas creio que isso não seja um grande problema.

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 

[Matheus Lima]

A propósito, minha implementação está com um desempenho da ordem de 10 milissegundos para o cálculo do determinante 100 x 100 em questão.

[Bruno Gouvêa]

Consegui eliminar o Laplace do código, porém ainda continua meio lento,

para uma matriz 100x100 demora cerca de 30 segundos para retornar o determinante,

não sei se o problema é ser em Python ou minha implementação do Gauss Jordan estar meio porca..

Porém, em Python não tive o problema da perca de precisão, pois existe uma classe "Fraction" que transforma pontos flutuantes em frações, e mantém dessa forma enquanto o resultado não for uma divisão exata!!

Tentei fazer o Gauss Jordan da forma mais simples possível (lembrando que ignoro os índices '0' da linha e coluna, considerando que a matriz inicia do índice '1'):

from fractions import Fraction

def detGaussJordan(matriz):

n = len(matriz)

aux = 1   ###aux guarda todos os numeros pelos quais sao divididos linhas da matriz

for i in range(1, n-1):

y = i+1   ###y guarda a próxima linha a ser permutada, caso necessário

while matriz[i][i] == 0 and y<n:

matriz[i], matriz[y] = matriz[y], matriz[i]   ###permuta as linhas 'i' e 'y'

y += 1

aux *= -1   ###apos permutação de linhas troca o sinal do determinante, conforme propriedades das matrizes

if matriz[i][i] != 0: 

x = matriz[i][i]

aux *= x

for j in range(i, n):   ###transforma todos os elementos da diagonal principal em '1', exceto o ultimo

matriz[i][j] = Fraction(matriz[i][j],x)

for j in range(i, n-1):   ###zera todos os elementos abaixo da diagonal principal, tornando a matriz triangular

fator = matriz[j+1][i]

for z in range(1, n):

matriz[j+1][z] -= (fator*matriz[i][z])

return aux * matriz[n-1][n-1]   ###retorna o determinante da matriz original

[Matheus Lima]

Acho que o problema é porque tu fica permutando as linhas da matriz várias vezes. Não precisa disso. Para achar o determinante Basta você transformar a matriz original em uma matriz triangular superior. Isso é feito substutuindo as linhas por combinações lineares de linhas que zerem os elementos abaixo da diagonal principal. E observe que adicionar uma linha vezes um escalar a outra linha da matriz não altera o valor do determinante. 

Sendo menos abstrato. Digamos que você queira inicialmente zerar todos os elementos abaixo do primeiro elemento da diagonal principal. Vamos começar pelo elemento logo abaixo. Vamos supor que o primeiro elemento da primeira linha seja "a" e o primeiro elemento da segunda linha seja "b". Sendo assim, para zerar o primeiro elemento da segunda linha, basta adicionar a primeira linha multiplicada por (-b/a) à segunda linha e substuir a segunda linha pelo resultado.

Após transformar a matriz em uma matriz triangular superior, bastar multiplicar todos os elementos da diagonal principal que o resultado será o determinante da matriz original.

Vamos agora demonstrar a validade da afirmação anterior. Vamos assumir que substituir uma linha por uma combinação linear dela com outra linha, o determinante não se altera. Vamos agora pegar uma matriz triangular superior e aplicar a regra de Laplace. Usando a primeira coluna, basta multiplicar o primeiro elemento pelo seu cofator, o resultado será o determinante da matriz triangular. Isso ocorre porque os elementos abaixo do primeiro elemento são zero. Porém, observe que o cofator do primeiro elemento da matriz triangular superior de ordem N, é o determinante de uma matriz triangular superior de ordem N-1. Esse cofator será igual ao primeiro elemento vezes o seu cofator, que é o determinante de uma matriz triangular superior de ordem N-2. Generalizando, o determinante da matriz triangular superior será o produto dos elementos da diagonal principal.

Como o processo de transformar uma matriz quadrada em uma matriz triangular superior por meio de combinações lineares não altera seu determinante, vemos que podemos fazer essa transformação em uma matriz qualquer para achar seu determinante.

Olhe a função determinant nesse meu código:

https://github.com/matheuslima/algebralinear/blob/master/gaussJordan.c

Eu uso a função para criar uma matriz aumentar unicamente porque minha função de calcular a matrix triangular pede uma matriz aumentada. Isso ocorre porque meu algorítmo inicialmente foi pensado para inverter matrizes ao invés de calcular determinantes.

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 

[Bruno Gouvêa]

E ah, no meu código o resultado para o seu exemplo de matriz foi: -396.18218219781704 

com o tempo de execução 112 segundos (muito lento)

Seu código parece estar mais preciso que o Octave!

[Bruno Gouvêa]

Matheus Lima, obrigado! 

Foi bastante esclarecedor sua ultima mensagem, tentarei me basear nisso pra tentar consertar meu metodo Gauss Jordan! 

 

[Walter Mascarenhas]

On Sunday, November 24, 2013 7:21:12 PM UTC-2, Bruno Gouvêa wrote:

Matheus Lima, obrigado! 

Foi bastante esclarecedor sua ultima mensagem, tentarei me basear nisso pra tentar consertar meu metodo Gauss Jordan! 

 

  1) Já que estamos na lista de C++, no fim de 2013, porque não tentar fazer o código
descrito nas mensagens acima em C++11? Ao invés de tantos apontadores, ficaria
mais legal ter uma classe Matrix, com o operator()(int i, int j). Assim daria para fazer
 matrix(i,j)  ao invés de matrix->conteudo[i][j]. 
   Claro, isso tudo é questão de opinião (O Linus diria que é frescura idiota), mas já
que estamos na lista de C++...

2) As trocas de linhas são inevitáveis. Por exemplo, considere a matrix

    0 1
    1 0
 

[Matheus Lima]

Sua sugestão é bem vinda Walter. Eu mesmo já havia pensado em migrar os códigos para C++, não o fiz ainda meramente por falta de tempo.

Lembra-se que há alguns meses atrás eu perguntei sobre se era melhor C ou C++ para sistemas matemáticos? Pois é, as sugestões que me foram dadas ainda serão aplicadas.

Com respeito as trocas de linha elas são sim inevitáveis. Mas pelo que entendi no código do Bruno ele fazia isso muito mais vezes que o necessário e isso aumenta o tempo de execução do código.

--

Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 

[Bruno Gouvêa]

Matheus Lima, na verdade, eu só estava permutando linhas quando encontrava um 0 na diagonal principal, não estava fazendo permutações desnecessárias, dei uma analisada e vi que o que o meu código estava fazendo não era muito diferente da sua sugestão...

Então não estava entendendo pq tanta demora na execução, já estava começando a pensar que o problema seria o Python mesmo...

Porém, descobri que o que estava deixando o código lento, era a classe "Fraction", que convertia pontos flutuantes em frações para o resultado ser preciso, troquei de Fraction para Float e a execução ficou instantânea, como o seu, porém com perda de precisão!!

Walter Mascarenhas, muito bem colocado! E peço desculpas por entrar com um código em Python numa lista de C++, mas foi o lugar onde encontrei um tópico que parecia se adequar mais! 

[Walter Mascarenhas]

 Bruno,

    O tradicional é permutar quando se encontra um número muito pequeno
na diagonal, porque uma divisão a / b com b muito muito menor que a
já pode levar um número enorme. Em geral, não é uma boa idéia escrever
algo assim

void fun(double x)
{
  if( x == 0.0) etc
}

 Por isso, eu encontraria a linha com o maior elemento na coluna
atual e faria uma permutação com ela. No fim das contas, o
custo das permutações será O(n^2) e a aritmética é O( n^3 ),
portanto as permutações não vão matar a sua performance.

  Matheus,

      Continuo pensando sobre as coisas que conversamos.
  Finalmente consegui achar tempo para voltar a trabalhar
  na minha biblioteca de álgebra linear em C++11 (e 14...)
  e recentemente consegui fundos da Fapesp para um
   projeto nesta área.

  Hoje tenho alguns alunos de mestrado e doutorado
  trabalhando em coisas ligadas as isso.

    Se alguém na lista tiver interesse em fazer mestrado
ou doutorado nesta área, me avise.

              walter.

[Matheus Lima]

Walter, 

Essa sua lib é código aberto? Se for, gostaria de contribuir com ela. O código da minha está nas primeiras implementações e acho que seria interessante eu colaborar com algum projeto já existente.

Abraço.

--
Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 

[Walter Mascarenhas]

  Bruno,

    É codigo aberto e o único jeito de ele ir para
a frente é ter mais colaboradores (Para fazer algo
legal dá um trabalho enorme.) Por isso sua ajuda,
e de outros membros da lista, seria bem vinda.
 
    Eu estou no meio de uma refatoração monstro
agora e não dá para te mandar o código. Mas semana
que vem eu posso te mandar.

    A idéia é poder trabalhar em C++ como em Matlab
ou Octave, ou  seja escrever coisas do tipo

   Vetor = Matrix * (10 * outro_vetor + col(matrix,5) ).

 A longo prazo o objetivo seria ter isto com performance
em máquinas multicore e Xeon Phi's.  Como sonhar é
de graça, seria legal também ter bindings para Python
e R etc. (Aliás, não tem nada errado em usar Python
nesta lista)

[P.]

Em segunda-feira, 25 de novembro de 2013 14h09min48s UTC-2, Walter Mascarenhas escreveu:

 

    É codigo aberto e o único jeito de ele ir para
a frente é ter mais colaboradores (Para fazer algo
legal dá um trabalho enorme.) Por isso sua ajuda,
e de outros membros da lista, seria bem vinda.

Onde está?

P. 

[P.]

Em segunda-feira, 25 de novembro de 2013 14h09min48s UTC-2, Walter Mascarenhas escreveu:

 

    É codigo aberto e o único jeito de ele ir para
a frente é ter mais colaboradores (Para fazer algo
legal dá um trabalho enorme.) Por isso sua ajuda,
e de outros membros da lista, seria bem vinda.
 
    Eu estou no meio de uma refatoração monstro
agora e não dá para te mandar o código. Mas semana
que vem eu posso te mandar.

oops, a resposta estava logo abaixo.... Hoje a cabeça está ruim.

Também estou aguardando. :-)

P. 

[Alan Silva]

Sim, esse tipo de trabalho muito me interessa também!

Compartilhe em algum repositório, quem sabe a galera daqui não possa ajudar!

[ ]'s

2013/12/5 P. <pedro....@gmail.com>

--

[Walter Mascarenhas]

  Vou compartilhar sim, só estou querendo deixar
a coisa um pouco mais limpa e organizada antes
de fazer isso (são por volta de cem arquivos .h,
e chega a quase trezentos se incluir os testes)
 
  Eu também gostaria de escrever um textinho
explicando um pouco as coisas, para quem
olhar o código não ficar completamente perdido.
Porém, a coisa está corrida neste fim de ano.

  Mesmo tendo que viajar a trabalho uns dias
na próxima semana, quero ver se posto
isto semana que vem.

   Vocês verão que tem muita coisa
para melhorar e para ser feita e, com
certeza, o pessoal aqui pode ajudar sim.

[augustowebd]

Srs sei que o nivel da thread está noutro patamar, mas seria possivel alguem me dizer onde que código como este seria allicado?

--
...vão-se os objetos, ficam-se as referências, passa o System.gc () e leva tudo...
PHP5 ZCE::ZEND004231 | $zendPHPCertified->getCandidateById( ZCE::ZEND004231 );
Fale sobre PHP::PHP-Brasília - Comunidade de usuários PHP do DF

[Matheus Lima]

Álgebra linear é a linguagem natural dos computadores. Isso já diz tudo.

Mas sendo mais específico, coisas como processamento de imagens e criptografia usam álgebra extensivamente.

[augustowebd]

Obrigado Matheus!

De fato agora recordo-me de ter estudado esta disciplina em criptografia, mas como atuou num ramo mais comercial de desenvolvimento não uso este tipo de recurso(determinantes), pelo menos diretamente.

[Walter Mascarenhas]

  Augusto,

   Álgebra linear é a base de muitas aplicações
em engenharia, física, estatística e finanças. 

  Há usuários tanto na academia como na
indústria e eu estou trabalhando neste
pacote com alguns casos de uso bem
concretos em mente (estimação de
parâmetros para modelos estatísticos
usados em finanças)

   Um exemplo da utilidade da álgebra
linear é o sucesso do Matlab. O meu
sonho (e de outros pacotes já
existentes) seria permitir algo
parecido com a programação
em matlab no C++11/14.
 
   Eu gostaria também de experimentar
com as features do C++11/14 e ver
como elas ajudariam na algebra
linear. Por exemplo, quando tivermos
"concepts" funcionando bem acredito
que daria para fazer código bem
limpo para isso (Por enquanto temos
que quebrar o galho com SFINAE)

  Em resumo, eu acredito que esta
é uma área boa para experimentar
novas idéias em C++ e produzir
algo útil. Se no fim da história o
projeto não ficar tâo bom pelo
menos acho que vale como
experimento.

Para sair dessa lista, envie um e-mail para ccppbrasil-unsubscribe@googlegroups.com

[augustowebd]

Walter muito agradecido pela explicação!