How to solve a linear system of the form A x <= b?

[matheusdiogenesandrade]

Hello.

I am trying to solve the linear system A x <= b, and I am trying to use the function sgesvx for this purpose. Although the function is made for problems of the form A x = b, I aim to add slack variables.

However, apparently, the functions is returning a wrong solution. For instance, let's take a look at the code below, which aims to solve the system - 0.33333 * x_1 - 0.06667 * x_2 = - 0.133333.

program Main

    implicit none

    external :: sgesv, sgesvx

    ! SCALAR 
    integer, parameter :: n=2,m=1
    integer :: i,j

    ! ARRAY 
    real(kind=8)    :: A(m,n),b(m),x(n)
    character(len=15)          :: subname

    ! LAPACK 
    integer                    :: IPIV(n),IWORK(n),INFO 
    character                  :: EQUED='N'
    real(kind=8)               :: R(n),C(n),RCOND,FERR(1),BERR(1),WORK(4*n),AF(m,n)

    !
    x(1) = 0
    x(2) = 0
    A(1,1) = -0.33333
    A(1,2) = -0.06667
    b(1) = -0.133333

    !
    do i = 1,m
        print *,"Constraint ",i,": "
        do j = 1,n
            print "(f10.5)",A(i,j)
        end do
        print *," = ",b(i)
    end do

    !
    call sgesvx( &
        'E', &
        'N', &
        n, &
        1, &
        A, &
        n, &
        AF, &
        n, &
        IPIV, &
        EQUED, &
        R, &
        C, &
        b, &
        n, &
        x, &
        n, &
        RCOND, &
        FERR, &
        BERR, &
        WORK, &
        IWORK, &
        INFO &
        )   

    if (INFO .lt. 0) then
        print *,INFO,"-th argument of sgesv is invalid"
    else if (INFO .gt. 0) then
        print *,INFO
    end if

    do j = 1,n
        print "(f10.5)",x(j)
    end do

end program Main

After compiling the program:

gfortran -O3 linearsystem.f90 -o main -lblas -llapack

And running it ./main, I get the following x solution:

• x_1 = 0.01346; And
• x_2 = 0.

That, when applied over the expression - 0.33333 * x_1 - 0.06667 * x_2 = - 0.133333, gives - 0.0044866218 = - 0.133333, which is invalid.

What is wrong with the snippet?

Thanks and regards.

[langou]

SGESVX is made for solving square linear system of equations with a square n-by-n matrix (and a right hand side of size n, and gives a solution of size n). In your code, you set n to 2. So LAPACK will solve a 2x2 system of equations. Since you only define (and allocate) the first row of your matrix, LAPACK is reading A(2,1) and A(2,2) somewhere in the memory system to solve a 2x2 system and the final result is indeed hard to interpret.

[matheusdiogenesandrade]

Ok, thanks. So which GESVX version would fit for my case? DGESV?

[langou]

For undetermined system of equations, there is xGELS. xGELS solves the minimum norm solution: min_{x s.t. Ax=b} || x ||_2. Beyond xGELS (and xGELSX), LAPACK provides factorizations and decompositions that can help you solve the problem at hand but there is not a driver so you have to call another library or build a solver yourself.

[matheusdiogenesandrade]

Thank you so much.