bugGNU Octave - Bugs: bug #67625, gmres requires erroneously too...

 
 

bug #67625: gmres requires erroneously too much memory

Submitter:  Marco Caliari <caliari>
Submitted:  Fri 24 Oct 2025 03:34:15 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Segfault, Bus Error, etc.
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * 10.3.0 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Post a Comment

Add a New Comment Rich Markup
   

Discussion

Sat 01 Nov 2025 01:27:26 AM UTC, comment #5: 

I had a further look and the gmres behavior follows Matlab.  So


a) I improved the documentation (difficult to understand as it is mainly a description of the technical algorithm with dual use parameters like maxit driven by exceptions and bordercases) and included point i: so documented on how to arrive to an exact solution (if it exists and assuming exact arithmetic).

b) I also further increased the Matlab compatibility: setting maxit to ceil(N / restart) instead of (N / restart).
Improving Matlab compatible behavior for dealing with (restart <= 0) || (maxit <= 0) was already done by Marco.

Make check is passed and a patch is attached.



(file #57759)

Hendrik K <koerhen>
Sun 26 Oct 2025 09:28:57 AM UTC, comment #4: 

ad i)

My understanding was that the Krylow solution space may be an issue: According to Wikipedia:

"After m iterations, where m is the size of the matrix A, the Krylov space K is the whole of m and hence the GMRES method arrives at the exact solution.". So by having a smaller Krylov space matrix (for memory reasons), does not prevent this arriving (in the worst case it may the be last one from what I read) at an exact solution ?

So maybe the documentation + default behavior should be changed as the default function parameter values does not guarantee that the exact solution cannot be found ? Or document this ?
 


ad iii) so does the documentation in gmres.m need to be changed when implementing the proposed patch ?

"help gmres"


Hendrik K <koerhen>
Sun 26 Oct 2025 08:37:48 AM UTC, comment #3: 

i) According to the documentation in the file gmres.m, if you want to perform exatly size_b iterations, you should call gmres(A,b,[],[],size_b). The dimension of Krylov subspace is correctly set to size_b (+1). If you call gmres(A,b,size_b,[],maxit) the documented behaviour, since restart = size_b, is that restart is not applied. Then, maxit iterations should be performed at most. If maxit is [], then min (size_b, 10) iterations should be performed at most.
Anyway, the new variable krylov_size is responsible only of the initialization of B,V,H. The actual number of iterations is not touched by the proposed patch.
ii) true, but if not provided, it was chosen as size_b, while the maximum number of iterations was min (size_b, 10). So, the allocated Krylov subspace was exagerately large.
iii) I do not know what that documentation is, and it is completely different from the documentation in gmres.m

Marco Caliari <caliari>
Group Member
Sun 26 Oct 2025 07:59:29 AM UTC, comment #2: 

A few questions:

i) are there any downsides of this approach ?
For example without studying the algorithm in detail, does reducing the Krylov subspace dimension not lead to potential sub-optimal approximation ? From what I read the GMRES method arrives at the exact solution (when n = m). So when no values are given for m when calling gmres with the current default sizing (restart = size_b), it is guaranteed to find the solution.
So the changes mean less memory albeit a potential less good solution ?

ii) One can always set the value/size of the Krylov subspace when providing m (which is the restart parameter). So the user can prevent memory issues according to his computer/problem size. Is this correct ?

iii) would not the gmres functional octave documentation be impacted ? Currently it states that  "m is the restart parameter, if not given or set to [] the default value numel (b) is used."
 "https://octave.so ... nction/gmres.html"

Hendrik K <koerhen>
Sat 25 Oct 2025 02:39:29 PM UTC, comment #1: 

I attach a new, simpler patch, in which I also change the behaviour for the corner cases in which restart or maxit are less or equal to 0 in input. The compatible result is to perform zero iterations, not to exit with an error.

(file #57741)

Marco Caliari <caliari>
Group Member
Fri 24 Oct 2025 03:34:15 PM UTC, original submission:  

The gmres routine for the solution of Ax=b initializes a Krylov subspace V with rows(x) rows and restart columns. This number of columns is exagerately large. For instance, this example


n = 50000;
A = sprand(n,n,1/n);
b = randn(n,1);
gmres(A,b);


kills octave on my system (32GB RAM). The correct number of columns depends on the values restart and maxit given in input. I attach a patch that should fix this problem (it is a simple diff, sorry for that).

Marco Caliari <caliari>
Group Member

 

Attached Files

Attached Files
file #57759:  67625.patch added by koerhen (3.5KiB - text/x-patch)
file #57741:  gmres2.patch added by caliari (945B - text/x-patch)
file #57738:  gmres.patch added by caliari (2.2KiB - text/x-patch)

(Note: upload size limit is set to 16MiB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

 

Dependencies

This item does not depend on any other items.

No items depend on this one.

 

Mail Notification Carbon-Copy List

Carbon-Copy List
  • -email is unavailable- added by koerhen (Posted a comment)
  • -email is unavailable- added by caliari (Submitted the item)
  •  

    Votes

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    History

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2025-11-01 koerhen Attached File- Added 67625.patch, #57759
    2025-10-25 caliari Attached File- Added gmres2.patch, #57741
    2025-10-24 caliari Attached File- Added gmres.patch, #57738

    Back to the top

    Powered by Savane 3.16.
    Corresponding source code