scipy: BUG: integrate: `solve_ivp` and `odeint` with `lsoda` have conflicting and unclear requirements for banded Jacobians

The lsoda method in solve_ivp does not honor uband and lband for banded jacobians.

Reproducing code example:

lsoda will never check the jacobian for a nonstiff problem, so I used the classical stiff Robertson ode and added trivial equations around it to make it banded.

odeint has no problem with the banded jacobian, but there is an error using solve_ivp.

from scipy.integrate import solve_ivp, odeint
import numpy as np

def f(t, y):
    return [
        y[0],
        -0.04 * y[1] + 1e4 * y[2] * y[3],
        0.04 * y[1] - 1e4 * y[2] * y[3] - 3e7 * y[2]**2,
        3e7 * y[2]**2,
        y[4]
    ]

def jac(t, y):
    return [
        [1,     0,                    0,         0, 0],
        [0, -0.04,             1e4*y[3],  1e4*y[2], 0],
        [0,  0.04, -1e4*y[3]-3e7*2*y[2], -1e4*y[2], 0],
        [0,     0,           3e7*2*y[2],         0, 0],
        [0,     0,                    0,         0, 1]
    ]

def band_jac(t, y):
    return [
        [0,     0,                    0,  1e4*y[2], 0],
        [0,     0,             1e4*y[3], -1e4*y[2], 0],
        [1, -0.04, -1e4*y[3]-3e7*2*y[2],         0, 1],
        [0,  0.04,           3e7*2*y[2],         0, 0]
    ]

rtol = 1e-8
atol = 1e-10

tspan = (0, 1000)
t_eval = np.linspace(*tspan, 100)
y0 = np.array([0, 1, 0, 0, 0])
method = 'LSODA'

sol = solve_ivp(f, tspan, y0, t_eval=t_eval, method='LSODA',
 rtol=rtol, atol=atol)
sol_jac = solve_ivp(f, tspan, y0, jac=jac, t_eval=t_eval, me
thod='LSODA', rtol=rtol, atol=atol)
assert np.allclose(sol.y, sol_jac.y)

y_odeint = odeint(f, y0, t_eval, tfirst=True, Dfun=jac)
assert np.allclose(sol.y, y_odeint.T)

y_odeint_band = odeint(f, y0, t_eval, tfirst=True, Dfun=band
_jac, ml=1, mu=2)
assert np.allclose(sol.y, y_odeint_band.T)

sol = solve_ivp(f, tspan, y0, lband=1, uband=2, jac=band_jac
, t_eval=t_eval, method='LSODA', rtol=rtol, atol=atol)
# error

Error message:

In this example it is looking for a matrix with 5 rows instead of the banded packed form matrix with 4 rows. Note that this is the size of the full dense jacobian. In my code (not given) where I was trying to debug the behavior, I have a much larger matrix and it also is looking for the full dense jacobian rather than the smaller packed one.

File "path/venv/lib/py
thon3.7/site-packages/scipy/integrate/_ode.py", line 1343, i
n run
    y1, t, istate = self.runner(*args)
ValueError: 0-th dimension must be fixed to 5 but got 4

Scipy/Numpy/Python version information:

import sys, scipy, numpy; print(scipy.__version__, numpy.__version__, sys.version_info)

1.3.1 1.17.1 sys.version_info(major=3, minor=7, micro=3, rel
easelevel='final', serial=0)

I haven’t been able to pinpoint the source of this yet.

About this issue

  • Original URL
  • State: closed
  • Created 7 years ago
  • Comments: 49 (32 by maintainers)

Most upvoted comments

@MatthewFlamm would you like to write the (temporary?) fix? I think all you have to do is add the banded Jacobian padding (in the spirit of the VODE one) in front of these lines:

I will do it. Thanks for the enlightening discussion on this issue that has plagued me for many years!

I think VODE should work because I noticed it has a shim function which pads the Jacobian (just like you say in your post a minute ago):

https://github.com/scipy/scipy/blob/9166b6fc4714fa55d4e829c8a76a278b8ecaf647/scipy/integrate/_ode.py#L1006-L1010

It seems like this wrapper is missing for class lsoda(ode).

@MatthewFlamm, so in odeint no extra rows are needed?

You can see from the original issue description code that it works without padding, as well as the gist code from https://github.com/scipy/scipy/issues/10793#issuecomment-2573975225. In https://github.com/scipy/scipy/issues/10793#issuecomment-2573484437, odeint will reject padding (either on top or bottom).

Here is where I think odeint does the memory copy to Fortran. jac_type == 4 is the banded user supplied Jacobian case we are discussing. I can’t follow everything, but it looks like it puts the user array at the beginning of the Fortran array in copy_array_to_fortran which means it is padded at the end (added: in the Fortran array, but not the user supplied array) as expected.

https://github.com/scipy/scipy/blob/9166b6fc4714fa55d4e829c8a76a278b8ecaf647/scipy/integrate/_odepackmodule.c#L363-L373

I can think of some fixes, but I’m not sure any are ideal given comments about moving away from using the Fortran code.

Number 5. would be the easiest. Instead of thinking for fixes, I would ask first what is the desired Python API (with padding or without padding). solve_ivp refers to the documentation of solve_banded which uses no padding:

     [*  * -1 -1 -1]
ab = [*  2  2  2  2]
     [5  4  3  2  1]
     [1  1  1  1  *]

If you look into the documentation of solve_banded it has to make a copy to accommodate the factorization (the overwrite_ab argument is meaningless in solve_banded, but meaningful for [s|d]gbsv):

https://github.com/scipy/scipy/blob/6e246d0b54dd55dc69232a0caae6772228a7ac25/scipy/linalg/_basic.py#L632-L636

But since LSODA isn’t using solve_banded this doesn’t actually matter. And the other SciPy ODE solvers don’t support the LAPACK banded format either. Only LSODA does.

I’m only 80 % certain of this, but the only way to avoid the making an internal copy of the Jacobian is if you add the padding on top and use order=F. Otherwise you won’t have the right layout for DGBTRF and a copy will be required. (In principle you could also use C order, but then you need to allocate the banded array of size n-by-2*ml+mu+1), i.e. tall and skinny.) But actually even this doesn’t help avoid a copy, because the callback format is jac(t,y):

def banded_jac(t,y,mu,ml) -> np.ndarray:
    ab = np.empty((mu+ml+1),len(y))    # allocate memory
    # ... fill ab ...
    return ab
    
sol = solve_ivp(..., 
    jac=lambda t, y: banded_jac(t,y,ml,mu),
    lband=ml,
    uband=mu,
    ...)

whereas the Fortran callback jac invoked within prja expects the Jacobian will be placed in the workspace memory (managed elsewhere):

 400  ml = iwm(1)
      mu = iwm(2)
      ml3 = ml + 3
      mband = ml + mu + 1
      meband = mband + ml
      lenp = meband*n
      do 410 i = 1,lenp
 410    wm(i+2) = 0.0d0
      call srcma (rsav, isav, 1)
      call jac (neq, tn, y, ml, mu, wm(ml3), meband)    ! jacobian goes into wm

So there is no way of avoiding the banded Jacobian array copy, unless you change the SciPy callback to a mutating one:

def jac(t,y,dFdy) -> None:
    # ... fill the values of dFdy[i,j] in-place ...

Just my two cents.


I hope my rambling is not confusing. I’ve come to the conclusion that this probably is a bug (call it a quirk if you want), because the wrappers are making a copy anyways, so why need to provide extra padding rows… This doesn’t make sense IMO. As we know, Python programming is about human efficiency, even if it comes at the cost a memory copy here and there.

That’s a very good observation.

If we borrow the DGBTRF image for a second KL = 2, KU = 1,

      *    *    *    +    +    +       *    *    *   u14  u25  u36
      *    *    +    +    +    +       *    *   u13  u24  u35  u46
      *   a12  a23  a34  a45  a56      *   u12  u23  u34  u45  u56
     a11  a22  a33  a44  a55  a66     u11  u22  u33  u44  u55  u66
     a21  a32  a43  a54  a65   *      m21  m32  m43  m54  m65   *
     a31  a42  a53  a64   *    *      m31  m42  m53  m64   *    *

the places marked by + are used for the factorization, and the * are ignored.

Let’s now focus on what we observe in the SciPy LSODA wrapper. You observed that in SciPy LSODA we have to fill the values like this,

      *   a12  a23  a34  a45  a56
     a11  a22  a33  a44  a55  a66
     a21  a32  a43  a54  a65   * 
     a31  a42  a53  a64   *    * 
      *    *    +    +    +    +    <--- extra padding (arguably missing 
      *    +    +    +    +    +    <--- from the SciPy docs...)

Since Fortran arrays are stored column-major, if you just imagine shifting the elements forward by ml while keeping the leading array dimension meband = 2*ml + mu + 1 fixed, this is actually equivalent to storing it like this

    wm(3)  *    *    +    +    +    +
           *    +    +    +    +    +
      *   a12  a23  a34  a45  a56       
     a11  a22  a33  a44  a55  a66
     a21  a32  a43  a54  a65   * 
     a31  a42  a53  a64   *    * 

The documentation in prja state the matrix is stored at wm(3) so that wm(3+ml) would be just the star above a11. This could explain how things work “correctly.” (Just not sure if it’s done like this deliberately. On second thought it is a nice indexing trick, and I can certainly imagine an F77 programmer doing it like this.)

Edit: This theory also fits with the factorization call:

https://github.com/scipy/scipy/blob/f5a3eafbb455e75afadbce223845149bda6d7a44/scipy/integrate/odepack/prja.f#L111-L113

So when you call the factorization, you pass wm(3), leaving the “extra room” on top of the top rows. But when you call the Jacobian routine, you pass wm(3+ml), which is akin to leaving the “extra room” in the bottom rows. Nifty. 😎

On the other hand, I’m guessing the days of LSODA are limited. Discussion here: https://github.com/scipy/scipy/issues/18566

However, DGBTRF states that the empty data should come first while we have found that the empty data has to come last. I have used my test case in the original description with the blank data first, and the # of function evaluations and # LU’s jumps dramatically. The result with the blank data last, matches the full dense Jacobian case in terms of function evals and LUs. This is good evidence that this is how it should be supplied even if it does not match expectation from DGBTRF. More work needs to be done in comparing different band structures.

Yep, that matches my own testing. 👍🏻 I found this a bit suspicious, but I didn’t dig deeper to find out if LSODA or the SciPy wrapper is shifting the rows into the position expected by the DGBTRF. Otherwise I don’t see how this could work.

I was sensitive to this issue, because in the past I noticed the difference in how DGBMV and DGBTRF need to be called (https://fortran-lang.discourse.group/t/help-with-blas-band-matrix-operations-solved/1150) - one has to pass the first element and leading dimension correctly, else you get a stair-case effect. An illustration of the leading dimension argument passing convention found in here (pg. 189 - 193): https://doku.lrz.de/dyn/Doku_Kurse/Fortran/basics/Fortran_3days.pdf

But we have found that it is possible that all of them work, but the requirements for the packing structure for the banded matrix is opaque and hard to figure out.

I would add here that using order='F' on the matrix should help avoid a temporary copy (at least that would be my expectation).

@lucascolley I’m not sure the title rename is correct here. I originally found that odeint was working, but solve_ivp / ode implementations did not work. This was a result of me first using odeint and then transitioning to solve_ivp when it was introduced.

But we have found that it is possible that all of them work, but the requirements for the packing structure for the banded matrix is opaque and hard to figure out. I will change the title to be more precise to what I think is going on at this point in time.

The workaround for me was to use odeint instead of solve_ivp or the ode implementation.