Documentation preview for this PR (built with commit 2b47e90; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

The order of operations could be improved by visiting the matrix by diagonals and stop as soon as a non zero value is found. it is best to visit simultaneously the upper and the lower diagonals.
You can use #39963 here.

I'm not sure that the method should be called bandwidth. May be get_bandwidth ? When you ask for the bandwidth, you usually expect to get an ordering of the rows/columns that minimizes the bandwidth.
See for instance method bandwidth in graphs https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/bandwidth.html

@dcoudert For the namesake, I wasn't careful to see that there is a method with the same name but different behavior implemented elsewhere. In that case, naming it the same would not be appropriate, will change to get_bandwidth. And additionally, I'm not sure if it would be necessary to propose implement bandwidth in matrix2.pyx as a follow-up issue.

As for using diagonal to improve efficiency, it was exactly what I thought when I created the diagonal PR and then got to this issue when looking for something similar in the issue pool. But as I understand it, the bandwidth of a matrix is the smallest distance for all non-zero entries to lie from the main diagonal. At that time, I felt iterating from main diagonal outward would not be an improvement (since it still needs to iterate to the end, in case a non-zero entry lies at the top corner).

So to clarify what you proposed, you're saying if I go through every diagonal starting from the corner to the main diagonal via diagonal, and I stop as soon as I reach a non-zero entry (and visit from both directions simultaneously), I would have an improvement with only $O(n^2)$ as the worst case scenario.

@dcoudert For the namesake, I wasn't careful to see that there is a method with the same name but different behavior implemented elsewhere. In that case, naming it the same would not be appropriate, will change to get_bandwidth. And additionally, I'm not sure if it would be necessary to propose implement bandwidth in matrix2.pyx as a follow-up issue.

I don't think it's necessary.

So to clarify what you proposed, you're saying if I go through every diagonal starting from the corner to the main diagonal via diagonal, and I stop as soon as I reach a non-zero entry (and visit from both directions simultaneously), I would have an improvement with only $O(n^2)$ as the worst case scenario.

Precisely and this is what was proposed in the original patch #13565. The idea is to stop computation as soon as possible. This should be an improvement for large matrix.

@dcoudert Hi so I've adjusted the get_bandwidth() method with the proposed algorithm. Unfortunately, I cannot come up with a cleaner way to construct the code than the status quo.

I don't think this will work for non-square matrices. You should add a test for this case. As such, I think it is better to split it into two separate loops. This way to can cleanly break out of each one and can account for the difference in the rows and columns.

Two minor points: (1) Please include the definition in the docstring. (2) EXAMPLES:: should be followed by a blankline.

@tscrim Hi a non-square matrix doctest is added, and I've fixed some minor bugs in the loop. They should work fine for both square and non-square now. Also adjusted for the empty line under EXAMPLE::

I have a doubt regarding the definition of bandwidth used in this PR. According the wikipedia page https://en.wikipedia.org/wiki/Band_matrix, it is the maximum of max_up and max_down, not the sum.
This is also the case in graphs, we use the max, not the sum.

I have a doubt regarding the definition of bandwidth used in this PR. According the wikipedia page https://en.wikipedia.org/wiki/Band_matrix, it is the maximum of max_up and max_down, not the sum. This is also the case in graphs, we use the max, not the sum.

That's a small technicality which can be easily changed. But it was by my search the sum of both. I'll look more into the page and get back on this issue.

if it's a max, you can do:

        for i in range(diag_range, 0, -1):
            if any(x != zero for x in self.diagonal(i)):
                max_up = i
                break
        for i in range(diag_range, max_up, -1):
            if any(x != zero for x in self.diagonal(-i)):
                return i
        return max_up

@dcoudert It would seem my initial search was misguided. I've changed the code and doctest accordingly

May be we can do even better like this:

        for i in range(diag_range, 0, -1):
            if (any(x != zero for x in self.diagonal(i))
                    or any(x != zero for x in self.diagonal(-i))):
                return i
        return 0

May be we can do even better like this:

@dcoudert Yes, that would significantly reduce the amount of code needed. I've pushed the latest version and tested out to make sure it works with past test cases.
I was skeptical before on creating a list each time and using the python any to check for the non-zero element because of all the extra space (though it's python so probably not a huge concern), so then I went for iteration. In this case, would adding 2 long checks in an if-statement be a good idea?

I'm not sure what you propose.
You can test on your side which form is the most efficient.
The current code is simple, but if you have something faster, it's always welcome.

I'm not sure what you propose.

@dcoudert I'm fine with your last suggestion, and have adjusted and pushed the code accordingly. I guess I was more talking about the coding style that I'm personally used to. But computation time wise, I think currently there's no other improvement. If it aligns with sage requirement, I'm happy with the status quo.