solving triadiagonal (and banded in general) systems of linear equations

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

solving triadiagonal (and banded in general) systems of linear equations

Sergei Steshenko


Hello,

performing web search I quickly came across http://www.gnu.org/software/octave/doc/interpreter/Basic-Matrix-Functions.html -> matrix_type , and in the latter I read:

"
'banded'
'banded positive definite'
Banded matrix with the band size of nl below the diagonal and nu above it.  If nl and nu are 1, then the matrix is tridiagonal and
treated with specialized code.  In addition the matrix can be marked as
probably a positive definite.  (Sparse matrices only)
...

Note that the matrix type will be discovered automatically on the first
attempt to solve a linear equation involving A.  Therefore matrix_type is only useful to give Octave hints of the matrix type.
Incorrectly defining the matrix type will result in incorrect results from
solutions of linear equations; it is entirely the responsibility of
the user to correctly identify the matrix type.
".

So, do I understand it correctly, that I simply need to provide matrix to the solver, and it will detect automatically that the matrix is banded and choose the most optimal algorithm ?


Matrix size is about 200 * 200, so do I need to specify it as a sparse matrix, or regular matrix should be OK ? Number of elements is about 4e4, the matrix is real, i.e. it should occupy 3.2e5 bytes which is not much by modern standards.

Thanks,
  Sergei.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: solving triadiagonal (and banded in general) systems of linear equations

Jordi Gutiérrez Hermoso-2
On 26 September 2012 18:48, Sergei Steshenko <[hidden email]> wrote:

> So, do I understand it correctly, that I simply need to provide
> matrix to the solver, and it will detect automatically that the
> matrix is banded and choose the most optimal algorithm ?

    http://hg.savannah.gnu.org/hgweb/octave/file/46dd555edd33/liboctave/array/MatrixType.cc#l268

Note that the argument for this function is a sparse matrix, so the
check only occurs for sparse matrices. For full matrices the check is

     http://hg.savannah.gnu.org/hgweb/octave/file/46dd555edd33/liboctave/array/MatrixType.cc#l60

only upper, lower, and hermitian matrices. No bandedness is checked if
the matrix isn't of sparse type. This is consistent with the
documentation:

    octave:1> x = toeplitz ([1 2 0 0 0 0]); y = toeplitz ([1 2 3 0 0 0]);
    octave:2> matrix_type (x), matrix_type (y)
    ans = Full
    ans = Full
    octave:3> matrix_type (sparse (x)), matrix_type (sparse (y))
    ans = Tridiagonal
    ans = Banded

HTH,
- Jordi G. H.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: solving triadiagonal (and banded in general) systems of linear equations

Sergei Steshenko


--- On Thu, 9/27/12, Jordi Gutiérrez Hermoso <[hidden email]> wrote:

> From: Jordi Gutiérrez Hermoso <[hidden email]>
> Subject: Re: solving triadiagonal (and banded in general) systems of linear equations
> To: "Sergei Steshenko" <[hidden email]>
> Cc: "Octave users list" <[hidden email]>
> Date: Thursday, September 27, 2012, 6:12 AM
> On 26 September 2012 18:48, Sergei
> Steshenko <[hidden email]>
> wrote:
>
> > So, do I understand it correctly, that I simply need to
> provide
> > matrix to the solver, and it will detect automatically
> that the
> > matrix is banded and choose the most optimal algorithm
> ?
>
>     http://hg.savannah.gnu.org/hgweb/octave/file/46dd555edd33/liboctave/array/MatrixType.cc#l268
>
> Note that the argument for this function is a sparse matrix,
> so the
> check only occurs for sparse matrices. For full matrices the
> check is
>
>      http://hg.savannah.gnu.org/hgweb/octave/file/46dd555edd33/liboctave/array/MatrixType.cc#l60
>
> only upper, lower, and hermitian matrices. No bandedness is
> checked if
> the matrix isn't of sparse type. This is consistent with
> the
> documentation:
>
>     octave:1> x = toeplitz ([1 2 0 0 0 0]); y =
> toeplitz ([1 2 3 0 0 0]);
>     octave:2> matrix_type (x), matrix_type (y)
>     ans = Full
>     ans = Full
>     octave:3> matrix_type (sparse (x)),
> matrix_type (sparse (y))
>     ans = Tridiagonal
>     ans = Banded
>
> HTH,
> - Jordi G. H.
>

So, can I explicitly specify type (banded) of traditional (not sparse) matrix ?

If yes, will it improve performance ?

Thanks,
  Sergei.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: solving triadiagonal (and banded in general) systems of linear equations

David Bateman-6




Le 27 sept. 2012 à 21:04, Sergei Steshenko <[hidden email]> a écrit :

>
>
> --- On Thu, 9/27/12, Jordi Gutiérrez Hermoso <[hidden email]> wrote:
>
>> From: Jordi Gutiérrez Hermoso <[hidden email]>
>> Subject: Re: solving triadiagonal (and banded in general) systems of linear equations
>> To: "Sergei Steshenko" <[hidden email]>
>> Cc: "Octave users list" <[hidden email]>
>> Date: Thursday, September 27, 2012, 6:12 AM
>> On 26 September 2012 18:48, Sergei
>> Steshenko <[hidden email]>
>> wrote:
>>
>>> So, do I understand it correctly, that I simply need to
>> provide
>>> matrix to the solver, and it will detect automatically
>> that the
>>> matrix is banded and choose the most optimal algorithm
>> ?
>>
>>     http://hg.savannah.gnu.org/hgweb/octave/file/46dd555edd33/liboctave/array/MatrixType.cc#l268
>>
>> Note that the argument for this function is a sparse matrix,
>> so the
>> check only occurs for sparse matrices. For full matrices the
>> check is
>>
>>      http://hg.savannah.gnu.org/hgweb/octave/file/46dd555edd33/liboctave/array/MatrixType.cc#l60
>>
>> only upper, lower, and hermitian matrices. No bandedness is
>> checked if
>> the matrix isn't of sparse type. This is consistent with
>> the
>> documentation:
>>
>>     octave:1> x = toeplitz ([1 2 0 0 0 0]); y =
>> toeplitz ([1 2 3 0 0 0]);
>>     octave:2> matrix_type (x), matrix_type (y)
>>     ans = Full
>>     ans = Full
>>     octave:3> matrix_type (sparse (x)),
>> matrix_type (sparse (y))
>>     ans = Tridiagonal
>>     ans = Banded
>>
>> HTH,
>> - Jordi G. H.
>>
>
> So, can I explicitly specify type (banded) of traditional (not sparse) matrix ?
>
> If yes, will it improve performance ?
>
> Thanks,
>  Sergei.
> _______________________________________________
> Help-octave mailing list
> [hidden email]
> https://mailman.cae.wisc.edu/listinfo/help-octave

You can explicitly set full matrix types as

Upper
Lower
Positive definite
Full
Singular

But you can't set it to "banded". In any case there is no banded full solver in octave

D,
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave