PowerBASIC --> Timing Matrix Inversions

[danbaron]

Here is a PowerBASIC program which times matrix inversions.

It was made with the PowerBASIC Console Compiler, version 5.
As it is, the program will not compile using the PowerBASIC Windows Compiler.

The program fills an N x N matrix with random doubles in the range of [0, 1),
and inverts it using the PowerBASIC internal function, "MAT INV()".
It times the inversion, and then writes the elapsed time, and a check vector to the file, "MATINV1.TXT".
If every value of the N-dimensional check vector is very close to 1, then the inversion is correct.

The program then fills the N x N matrix again with the same set of random doubles,
and inverts it using the coded subroutine (in the program), "INV2()".
It times the inversion, and then writes the elapsed time, and a check vector to the file, "MATINV2.TXT".
If every value of the N-dimensional check vector is very close to 1, then the second inversion is also correct.

The program runs in a console window, and writes its progress in the window, as it executes.

"INV2()", is coded as a subroutine, because the compiler does not permit users to code functions which return arrays.

The program could be modified to compile using the PowerBASIC Windows Compiler. But, I am not sufficiently motivated to do it.

I noticed one interesting phenomenon. Each time the program runs, two check vectors are written to files,
one for the inversion using PowerBASIC's function, "MAT INV()", and the other for the inversion using the coded subroutine, "INV2()".
For every program run, my experience is that the two check vectors are exactly identical to each other.

I ran the program three times for a 1000 x 1000 matrix.

I.F. = PowerBASIC's internal function, "MAT INV()"
C.S. = the program's coded subroutine, "INV2()"

The times were (seconds),

I.F. ***C.S.
105.881 54.896
104.301 54.863
104.918 55.051

I attached the program file below. I called it, "MATINV.TXT".
(The forum will not permit me to attach a file with the extension, "BAS".)
If you download it, then rename it to, "MATINV.BAS", before you compile it.

(If, by chance, an inversion starts before midnight, and finishes after midnight, the elapsed time for it will be wrong (crazily wrong).)


Dan

'************************************************************************************************************

' FILE = "MATINV.BAS"

' Made with the PowerBASIC Console Compiler, version 5.
' As it is, the program will not compile using the PowerBASIC Windows Compiler.

' The program fills an N x N matrix with random doubles in the range of [0, 1),
' and inverts it using the PowerBASIC internal function, "MAT INV()".
' It times the inversion, and then writes the elapsed time, and a check vector to the file, "MATINV1.TXT".
' If every value of the N-dimensional check vector is very close to 1, then the inversion is correct.

' The program then fills the N x N matrix again with the same set of random doubles,
' and inverts it using the coded subroutine shown below, "INV2()".
' It times the inversion, and then writes the elapsed time, and a check vector to the file, "MATINV2.TXT".
' If every value of the N-dimensional check vector is very close to 1, then the second inversion is also correct.

' "INV2()", is coded as a subroutine, because the compiler does not permit users to code functions which return arrays.

' The program could be modified to compile using the PowerBASIC Windows Compiler. But, I am not sufficiently motivated to do it.

' I noticed one interesting phenomenon. Each time the program runs, two check vectors are written to files,
' one for the inversion using PowerBASIC's function, "MAT INV()", and the other for the inversion using the coded subroutine, "INV2()".
' For every program run, my experience is that the two check vectors are exactly identical to each other.

'************************************************************************************************************

#COMPILE EXE
#DIM ALL

'Set the size of the N x N matrix to invert, on the next line.
%N = 1000

$FN1 = "MATINV1.TXT"
$FN2 = "MATINV2.TXT"

GLOBAL DATE AS STRING
GLOBAL TIME AS STRING

'************************************************************************************************************
'************************************************************************************************************
'************************************************************************************************************

FUNCTION PBMAIN() AS LONG

DIM T0 AS DOUBLE
DIM T1 AS DOUBLE
DIM T2 AS DOUBLE
DIM TT AS DOUBLE
DIM A0(1 TO %N, 1 TO %N) AS DOUBLE
DIM AI(1 TO %N, 1 TO %N) AS DOUBLE
DIM ID(1 TO %N, 1 TO %N) AS DOUBLE
DIM VA(1 TO %N) AS DOUBLE
DIM VB(1 TO %N) AS DOUBLE

'---------------------------------------------

DATE = DATE$
TIME = TIME$

T0 = TIMER

'---------------------------------------------

CALL CONSOLEOUTPUT(1, TT)

RANDOMIZE T0
CALL INITIALIZEARRAYS(A0(), AI(), VA())

T1 = TIMER
MAT AI() = INV(A0())
T2 = TIMER
TT = T2 - T1

CALL CONSOLEOUTPUT(2, TT)

MAT ID = A0 * AI
MAT VB = ID * VA

CALL WRITEFILE(1, VB(), TT)

CALL CONSOLEOUTPUT(3, TT)

'---------------------------------------------

RANDOMIZE T0
CALL INITIALIZEARRAYS(A0(), AI(), VA())

T1 = TIMER
CALL INV2(AI())
T2 = TIMER
TT = T2 - T1

CALL CONSOLEOUTPUT(4, TT)

MAT ID = A0 * AI
MAT VB = ID * VA

CALL WRITEFILE(2, VB(), TT)

'---------------------------------------------

CALL CONSOLEOUTPUT(5, TT)
WAITKEY$

END FUNCTION

'************************************************************************************************************
'************************************************************************************************************
'************************************************************************************************************

SUB INITIALIZEARRAYS(A1() AS DOUBLE, A2() AS DOUBLE, V() AS DOUBLE)
LOCAL FIRST AS LONG
LOCAL LAST AS LONG
LOCAL N AS LONG
LOCAL I AS WORD
LOCAL J AS WORD
LOCAL D AS DOUBLE

FIRST = LBOUND(A1(1))
LAST = UBOUND(A2(1))
N = LAST - FIRST + 1

FOR I = FIRST TO LAST
V(I) = 1
FOR J = FIRST TO LAST
D = RND
A1(I, J) = D
A2(I, J) = D
NEXT
NEXT
END SUB

'************************************************************************************************************
'************************************************************************************************************
'************************************************************************************************************

SUB CONSOLEOUTPUT(WHICHTIME AS BYTE, T AS DOUBLE)
LOCAL SO AS STRING
LOCAL SN AS STRING
LOCAL ST AS STRING

SN = STR$(%N)
ST = FORMAT$(T, "0000.000")

SELECT CASE WHICHTIME

CASE 1
SO = "Inverting a" & SN & " by" & SN & " matrix the first time,"
PRINT
PRINT SO
PRINT "using PowerBASIC's internal function, ""MAT INV()"".."
PRINT

CASE 2
PRINT "Finished.
PRINT
SO = "elapsed time = " & ST & " seconds"
PRINT SO
PRINT
PRINT "Calculating and writing the first check vector.."
PRINT

CASE 3
PRINT "Finished.
PRINT
SO = "Inverting the" & SN & " by" & SN & " matrix the second time,"
PRINT SO
PRINT "using the coded subroutine, ""INV2()"".."
PRINT

CASE 4
PRINT "Finished.
PRINT
SO = "elapsed time = " & ST & " seconds"
PRINT SO
PRINT
PRINT "Calculating and writing the second check vector.."
PRINT

CASE 5
PRINT "All finished.
PRINT
PRINT "Press ""Enter"" to quit."
PRINT

CASE ELSE
PRINT "Something wrong."
PRINT

END SELECT

END SUB

'************************************************************************************************************
'************************************************************************************************************
'************************************************************************************************************

SUB WRITEFILE(WHICHTIME AS BYTE, V() AS DOUBLE, T AS DOUBLE)
LOCAL FIRST AS LONG
LOCAL LAST AS LONG
LOCAL N AS LONG
LOCAL I AS LONG
LOCAL FN AS STRING
LOCAL S1 AS STRING
LOCAL S2 AS STRING
LOCAL SN AS STRING
LOCAL SO AS STRING
LOCAL ST AS STRING

FIRST = LBOUND(V(1))
LAST = UBOUND(V(1))
N = LAST - FIRST + 1

SN = STR$(N)
ST = FORMAT$(T, "0000.000")

IF (WHICHTIME = 1) THEN
FN = $FN1
SO = "PowerBASIC's internal function, ""MAT INV()""."
ELSE
FN = $FN2
SO = "the coded subroutine, ""INV2()""."
END IF

OPEN FN FOR OUTPUT AS #1

S1 = "FILE = """ & FN & """
PRINT#1, S1
S1 = DATE & ", " & TIME & "."
PRINT#1, S1
PRINT#1
S1 = "Inversion of a" & SN & " by" & SN & " matrix,"
PRINT#1, S1
PRINT#1, "filled with uniformly distributed random doubles,"
PRINT#1, "in the range of [0, 1),"
S1 = "using " & SO
PRINT#1, S1
PRINT#1
S1 = "elapsed time = " & ST & " seconds"
PRINT#1, S1
PRINT#1
PRINT#1, "If the inversion was calculated correctly, then every"
PRINT#1, "value shown below should be very close to 1."
PRINT#1
PRINT#1, "Index      Value"

FOR I = FIRST TO LAST
S1 = FORMAT$(I, "0000")
S1 = S1 & "  "
S2 = FORMAT$(V(I), "0.00000000000000000000")
S1 = S1 & S2
PRINT#1, S1
NEXT

CLOSE #1

END SUB

'************************************************************************************************************
'************************************************************************************************************
'************************************************************************************************************

SUB INV2(A() AS DOUBLE)
'Uses the Gauss-Jordan Method.
'Inverts matrix, A(), "in-place". 

LOCAL PIVOT AS LONG
LOCAL ROW AS LONG
LOCAL COL AS LONG
LOCAL MAXROW AS LONG
LOCAL TEST AS DOUBLE
LOCAL COLMAX AS DOUBLE
LOCAL DIVISOR AS DOUBLE
LOCAL FACTOR AS DOUBLE
LOCAL TEMP AS DOUBLE
LOCAL ROWSWITCH AS LONG
LOCAL SWITCHCOUNT AS LONG
LOCAL FIRST AS LONG
LOCAL LAST AS LONG
LOCAL N AS LONG

'---------------------------------------------

FIRST = LBOUND(A(1))
LAST = UBOUND(A(1))
N = LAST - FIRST + 1

DIM ROWSWITCHES(1 TO N, 1 TO 2) AS LONG

SWITCHCOUNT = 0

FOR PIVOT = FIRST TO LAST

COLMAX = 0
MAXROW = PIVOT

'---------------------------------------------

FOR ROW = PIVOT TO LAST
TEST = ABS(A(ROW, PIVOT))
IF( TEST > COLMAX) THEN
COLMAX = TEST
MAXROW = ROW
END IF
NEXT

'---------------------------------------------

IF(MAXROW <> PIVOT) THEN
FOR COL = FIRST TO LAST
TEMP = A(PIVOT, COL)
A(PIVOT, COL) = A(MAXROW, COL)
A(MAXROW, COL) = TEMP
NEXT

SWITCHCOUNT = SWITCHCOUNT + 1
ROWSWITCHES(SWITCHCOUNT, 1) = PIVOT
ROWSWITCHES(SWITCHCOUNT, 2) = MAXROW
END IF

'---------------------------------------------

DIVISOR = A(PIVOT, PIVOT)
A(PIVOT, PIVOT) = 1

FOR COL = FIRST TO LAST
A(PIVOT, COL) = A(PIVOT, COL) / DIVISOR
NEXT

'---------------------------------------------

FOR ROW = FIRST TO LAST

IF(ROW <> PIVOT) THEN

FACTOR = -A(ROW, PIVOT)
A(ROW, PIVOT) = 0

FOR COL = FIRST TO LAST
A(ROW, COL) = A(ROW, COL) + A(PIVOT, COL) * FACTOR
NEXT

END IF
NEXT

NEXT

'---------------------------------------------

FOR ROWSWITCH = SWITCHCOUNT TO 1 STEP -1
FOR ROW = FIRST TO LAST
TEMP = A(ROW, ROWSWITCHES(ROWSWITCH, 1))
A(ROW, ROWSWITCHES(ROWSWITCH, 1)) = A(ROW, ROWSWITCHES(ROWSWITCH, 2))
A(ROW, ROWSWITCHES(ROWSWITCH, 2)) = TEMP
NEXT
NEXT

END SUB

'************************************************************************************************************
'************************************************************************************************************
'************************************************************************************************************

[jack]

my timings
I.F 40.096
C.S 23.126

[danbaron]

Now I see that Bob made a big matrix class in PowerBasic.

http://www.powerbasic.com/support/pb...ad.php?t=45876

I downloaded and looked a little bit at it.

It seems to be careful, meticulous, and big.

I saw FFT there.

(The problem I see with programmers communicating with each other (me too) is, that each one ONLY wants everyone else to look at what he did.)

So, I looked at the matrix inversion program (above) I made before with PowerBasic.

It still runs using PBCC6.

' output ------------------------------------------------------------------------------------------------

Inverting a 1000 by 1000 matrix the first time,
using PowerBASIC's internal function, "MAT INV()"..

Finished.

elapsed time = 0111.368 seconds

Calculating and writing the first check vector..

Finished.

Inverting the 1000 by 1000 matrix the second time,
using the coded subroutine, "INV2()"..

Finished.

elapsed time = 0057.237 seconds

Calculating and writing the second check vector..

All finished.

Press "Enter" to quit.

[REDEBOLT]

pbcc 6.02.0099

i.f. ***c.s.
119.013 39.967
104.301 54.863
104.918 45.708


pbcc 5.05.0131

i.f. ***c.s.
136.765 53.929
143.521 54.863
108.670 53.290

[danbaron]

When I made the program, I used DOUBLEs as the data type, because, I wanted to compare the times using other languages, and some of them do not have EXTs.

But, I remembered something I thought I had read about PowerBasic EXTs, and I found it in the PBCC6 help, by searching for, "ext",

"In PowerBASIC, all floating point calculations are performed in extended precision for maximum accuracy.".

So, I thought, in that case, the program should run faster if I use EXTs as the data type, because then PowerBasic will not have to convert the result to DOUBLEs.

So, I tried an experiment.

In the code above, I globally replaced "DOUBLE", with, "EXT", and then I ran the program again.

But, it didn't run faster, in fact it took over twice as long.

Does it make sense?

' output -------------------------------------------------------------------------

Inverting a 1000 by 1000 matrix the first time,
using PowerBASIC's internal function, "MAT INV()"..

Finished.

elapsed time = 0236.840 seconds

Calculating and writing the first check vector..

Finished.

Inverting the 1000 by 1000 matrix the second time,
using the coded subroutine, "INV2()"..

Finished.

elapsed time = 0126.828 seconds

Calculating and writing the second check vector..

All finished.

Press "Enter" to quit.

[kryton9]

I don't know the math part Dan. But from what I have read of forums, Doubles are the fastest processed on computers and Longs for Whole Numbers.