Simultaneous equations with random coefficients go through Gaussian elimination - awfully slow if you have 100+ rows. I know Toeplitz, tridiagonal and pentadiagonal have special solutions that are much faster. Any other matrix that has a more efficient algorithm to solve?
what matrices are easiest to invert?
Started by ●October 24, 2016
Reply by ●October 24, 20162016-10-24
On 24.10.2016 12:00, pedro1492@lycos.com wrote:> Simultaneous equations with random coefficients go through Gaussian > elimination - awfully slow if you have 100+ rows. > I know Toeplitz, tridiagonal and pentadiagonal have special solutions > that are much faster. Any other matrix that has a more efficient > algorithm to solve? >Unitary matrix. (Sorry. Couldn't resist the joke.) Gene
Reply by ●October 24, 20162016-10-24
On 24.10.2016 12:09, Evgeny Filatov wrote:> On 24.10.2016 12:00, pedro1492@lycos.com wrote: >> Simultaneous equations with random coefficients go through Gaussian >> elimination - awfully slow if you have 100+ rows. >> I know Toeplitz, tridiagonal and pentadiagonal have special solutions >> that are much faster. Any other matrix that has a more efficient >> algorithm to solve? >> > > Unitary matrix. (Sorry. Couldn't resist the joke.) > > Gene >I've just opened the Wikipedia, and seen the article "Matrix decomposition", from which it's clear that Gaussian elimination is not the only way to solve a linear system of equations: https://en.wikipedia.org/wiki/Matrix_decomposition Have you considered options discussed at that page? For example, if your matrix is hermitian and positive definite, you could use Cholesky decomposition which is said to be twice as effective as Gaussian elimination. Depending on the task, sometimes you don't need to solve the entire system, but need just a few eigenvalues (and eigenvectors). There are optimized methods to do that, too. Evgeny
Reply by ●October 24, 20162016-10-24
Am 24.10.16 um 11:00 schrieb pedro1492@lycos.com:> Simultaneous equations with random coefficients go through Gaussian > elimination - awfully slow if you have 100+ rows. > I know Toeplitz, tridiagonal and pentadiagonal have special solutions > that are much faster. Any other matrix that has a more efficient > algorithm to solve? >Orthogonal matrix. It is just the transposition or complex conjugate. Those are also important, think of DFT for instance, or coordinate system transforms. Christian
Reply by ●October 24, 20162016-10-24
>Am 24.10.16 um 11:00 schrieb pedro1492@lycos.com: >> Simultaneous equations with random coefficients go through Gaussian >> elimination - awfully slow if you have 100+ rows. >> I know Toeplitz, tridiagonal and pentadiagonal have special solutions >> that are much faster. Any other matrix that has a more efficient >> algorithm to solve? >> >Orthogonal matrix. It is just the transposition or complex conjugate. >Those are also important, think of DFT for instance, or coordinate >system transforms. > > ChristianA small correction, I think you meant "orthonormal" instead of "orthogonal". My answer was going to be a diagonal matrix. They are really easy to invert. Ced --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●October 24, 20162016-10-24
On 24.10.2016 21:35, Cedron wrote:>> Am 24.10.16 um 11:00 schrieb pedro1492@lycos.com: >>> Simultaneous equations with random coefficients go through Gaussian >>> elimination - awfully slow if you have 100+ rows. >>> I know Toeplitz, tridiagonal and pentadiagonal have special solutions >>> that are much faster. Any other matrix that has a more efficient >>> algorithm to solve? >>> >> Orthogonal matrix. It is just the transposition or complex conjugate. >> Those are also important, think of DFT for instance, or coordinate >> system transforms. >> >> Christian > > A small correction, I think you meant "orthonormal" instead of > "orthogonal". > > My answer was going to be a diagonal matrix. They are really easy to > invert. > > Ced > --------------------------------------- > Posted through http://www.DSPRelated.com >Sure thing, Ced. Could you, please, invert for me the following diagonal matrix? 1 0 0 0 1 0 0 0 0 I would really appreciate your effort! Kindly thanks, Gene
Reply by ●October 24, 20162016-10-24
On 24.10.16 11.00, pedro1492@lycos.com wrote:> Simultaneous equations with random coefficients go through Gaussian > elimination - awfully slow if you have 100+ rows.Sure? Numerical recipies recommends LU decomposition.> I know Toeplitz, tridiagonal and pentadiagonal have special solutions > that are much faster. Any other matrix that has a more efficient > algorithm to solve?Of course, unity matrix, unitary matrix, orthogonal matrix ... ;-) Marcel
Reply by ●October 24, 20162016-10-24
On Mon, 24 Oct 2016 23:41:47 +0300, Evgeny Filatov <e.v.filatov@ieee.org> wrote:>On 24.10.2016 21:35, Cedron wrote: >>> Am 24.10.16 um 11:00 schrieb pedro1492@lycos.com: >>>> Simultaneous equations with random coefficients go through Gaussian >>>> elimination - awfully slow if you have 100+ rows. >>>> I know Toeplitz, tridiagonal and pentadiagonal have special solutions >>>> that are much faster. Any other matrix that has a more efficient >>>> algorithm to solve? >>>> >>> Orthogonal matrix. It is just the transposition or complex conjugate. >>> Those are also important, think of DFT for instance, or coordinate >>> system transforms. >>> >>> Christian >> >> A small correction, I think you meant "orthonormal" instead of >> "orthogonal". >> >> My answer was going to be a diagonal matrix. They are really easy to >> invert. >> >> Ced >> --------------------------------------- >> Posted through http://www.DSPRelated.com >> > >Sure thing, Ced. Could you, please, invert for me the following diagonal >matrix? > >1 0 0 >0 1 0 >0 0 0 > >I would really appreciate your effort! > >Kindly thanks, >Genelulz "Orthonormal" applies to vector sets, although an orthonormal set can be used to make an orthogonal matrix. Has nobody mentioned the identity matrix yet as an example of "easiest to invert"?
Reply by ●October 24, 20162016-10-24
Am 25.10.16 um 00:18 schrieb Marcel Mueller:> On 24.10.16 11.00, pedro1492@lycos.com wrote: >> Simultaneous equations with random coefficients go through Gaussian >> elimination - awfully slow if you have 100+ rows. > > Sure? Numerical recipies recommends LU decomposition.LU decomposition is the same as Gaussia elimination. It is of the order O(N^3) flops for square matrices. The question is, what exactly means "slow". A 100x100 system is solved in a millisecond using LU decomposition on a desktop computer. "Slow" always depends on your expectations, whereas for a 1000x1000 system you'll need a second. For a dense system, you cannot do much better than that - however if you have a sparse system, then from a certain point on an iterative method like conjugate gradients will be faster. Christian
Reply by ●October 24, 20162016-10-24
On Tue, 25 Oct 2016 00:59:50 +0200, Christian Gollwitzer <auriocus@gmx.de> wrote:>Am 25.10.16 um 00:18 schrieb Marcel Mueller: >> On 24.10.16 11.00, pedro1492@lycos.com wrote: >>> Simultaneous equations with random coefficients go through Gaussian >>> elimination - awfully slow if you have 100+ rows. >> >> Sure? Numerical recipies recommends LU decomposition. > >LU decomposition is the same as Gaussia elimination. It is of the order >O(N^3) flops for square matrices. The question is, what exactly means >"slow". A 100x100 system is solved in a millisecond using LU >decomposition on a desktop computer. "Slow" always depends on your >expectations, whereas for a 1000x1000 system you'll need a second. For a >dense system, you cannot do much better than that - however if you have >a sparse system, then from a certain point on an iterative method like >conjugate gradients will be faster. > > ChristianI thought everybody was using SVD these days?
