Reduced Row-Echelon Form of a Matrix Help

[brettc431]

Before I get started on the help I need I will say that yes this is a project for school so I'm not looking for anyone to give me the code but my group is new to MASM and struggling to get the code.  We understand how to find the RREF on paper, but not through code.  Here is our assignment:

Row-Echelon Matrix Reduction
Write a program that calculates the row-echelon form of a matrix of any size. The matrix values are all integer and stored in an input file. The reduced matrix is stored in an output file. The values of the output matrix should also be integer values.


And here is our current code, it's bad we know:

Code Select Expand

.MODEL SMALL ;Defines memory model as small which uses separate segments for code and data
.386 ;Microprocessor number
.STACK ;Stack segment defined as 1024 by default
.DATA ;Begins definition of the data type used in this project

ROW DB ?
COLUMN DB ?
RREF DB "matrix.txt", 0

.CODE

;-------------------------------------------------------------------------------------------
READ MACRO
MOV CX, LENGTHOF RREF
MOV DX, OFFSET RREF
MOV AH, 3FH ;Read
INT 21H
JC QUIT
CMP AX, 1
JNE QUIT

;-------------------------------------------------------------------------------------------

Main PROC FAR ;Defines procedure distance as far
.STARTUP 
;Program:

MOV BP, 0
MOV SI, 0

MOV AX, 3D02h ;Open file
MOV DX, OFFSET RREF
INT 21H
MOV BX, AX


IF ROW<COLUMN
D=ROW
IF ROW>COLUMN
D=COLUMN
FOR d=1...D
e=M(d,d)
FOR r=d...(ROW-1)
X=M(ROW,d)/e
FOR col=d...COLUMN
M(r,col)=M(r,col)-e*X





PUSH BP

MOV BP, SP

CALL REDUCTION
JC QUIT
ADD SP 2+4
POP BP


MOV AH,40h
INT 21H

MOV AH, 3Eh
INT 21H

QUIT: .EXIT
MAIN ENDP


REDUCTION PROC
PUSHAD

MOVZX EAX, ROW
MOV EDX, EAX
MOVZX EBX, COLUMN
SUB EBX, 1
MUL EBX
JC QUIT
SUB EDX, 1
ADD EAX, EDX

JC QUIT
LOOP
POPAD
RET
REDUCTION ENDP

END


The code itself is all over the place.  We have to open a file from MATLAB containing a matrix in the form [R,C,#,#,#,#,#,#,#,#,#,#, etc.] where the first two bytes are the row and column numbers respectively, and the rest are the elements of the matrix stored in 8 bytes each.  The matrix can go all the way to R-C dimensions of 255,255 but that is randomly generated in MATLAB.  Once we open and read the file, we have to calculate the reduced row echelon form with only the elements below the diagonal zeroed out, everything above the diagonal doesn't matter.  Then we must write the RREF matrix to an output file to be opened in MATLAB and displayed.

Any and all help will be greatly appreciated, we just need to be steered in the right direction.  Here is our trouble:

1. How to read two separate bytes, then each element, which are 8 bytes long a piece, and what to do with them
2. How to code for reducing the lower half of the matrix
3. How to write to an output file

Programs we are using are Textpad 6 and Codeview debugger

[FORTRANS]

Hi,

1. How to read two separate bytes,

   Using parts of your code, it would look something like the
following.

Code Select Expand


        MOV     CX,2    ; Want to read two bytes.
        MOV     DX, OFFSET ROW
        MOV     AH, 3FH ;Read
        INT     21H
        JC      QUIT
        CMP      AX, 2
        JNE     QUIT

   That will place one byte in ROW and one in COLUMN.

then each element, which are 8 bytes long a piece

   Well, change the 2 to an 8 in the above code and point to an
element buffer, and you can read them in one at a time.  Or
multiply the row times the column times 8 and read them in all at
once.  Remember to allocate enough space to hold the whole lot.

and what to do with them

   Find the MATLAB documentation and find what format the
elements are stored in.  Real4 and integers are possible.

Regards,

Steve N.

[jj2007]

   Find the MATLAB documentation and find what format the
elements are stored in.  Real4 and integers are possible.

MatLab is normally REAL8 aka "double". However, two bytes for rows and columns at the beginning is not a standard MatLab matrix. Only your supervisor knows what format that is. My best guess is 2 bytes R+C plus REAL8 elements. Which is a lousy format for performance reasons (badly aligned) but technically it can work, if you have no more that 256 rows...

[FORTRANS]

MatLab is normally REAL8 aka "double".

Hi,

   Yes, my mistake.  Thanks for the correction.

However, two bytes for rows and columns at the beginning is not a standard MatLab matrix. Only your supervisor knows what format that is. My best guess is 2 bytes R+C plus REAL8 elements. Which is a lousy format for performance reasons (badly aligned) but technically it can work, if you have no more that 256 rows...

   At any rate, they need to know what the elements in the file
are.  And I would hope no more than a 10x10 matrix.  I would
not think alignment in the file would hurt amything?  Alignment
in memory can hurt.  But if getting a working program is the
goal, I would leave that to last to worry about.

Regards,

Steve N.

[RuiLoureiro]

   Find the MATLAB documentation and find what format the
elements are stored in.  Real4 and integers are possible.

MatLab is normally REAL8 aka "double". However, two bytes for rows and columns at the beginning is not a standard MatLab matrix. Only your supervisor knows what format that is. My best guess is 2 bytes R+C plus REAL8 elements. Which is a lousy format for performance reasons (badly aligned) but technically it can work, if you have no more that 256 rows...

Jochen, he said each element of matrix is 8 bytes, not real 8.
                read it again else where [R, C ...]... :icon14:

[brettc431]

and what to do with them

   Find the MATLAB documentation and find what format the
elements are stored in.  Real4 and integers are possible.

Thanks for the help so far.  The matrix elements in the input and output file are both stored as integers.  The max matrix size, as told by our instructor, will be 255x255.  Our code needs to be able to read the row and column inputs, decide which of the values is smaller so that the correct diagonal can be setup, then loop all the way through the matrix beneath the diagonal to zero-out the elements.

Also, the file format is 2 bytes (R & C) then all the elements separated by one space each.  i.e. R C (element) (element) (element) (element) (element) etc.

[FORTRANS]

Thanks for the help so far.  The matrix elements in the input and output file are both stored as integers.  The max matrix size, as told by our instructor, will be 255x255.  Our code needs to be able to read the row and column inputs, decide which of the values is smaller so that the correct diagonal can be setup, then loop all the way through the matrix beneath the diagonal to zero-out the elements.

Also, the file format is 2 bytes (R & C) then all the elements separated by one space each.  i.e. R C (element) (element) (element) (element) (element) etc.

Hi,

   Well the two bytes for row and column are obviously binary
values if they can be as large as 255.  Elements separated by
spaces sounds a bit odd.  Are the integers ASCII (text) or
binary?  Are the spaces part of the eight bytes or are there nine
bytes per matrix entry?  These questions are minor considerations
anyway.  Reading the data into your program should be relatively
easy.

   Just reading the file into memory and writing it back out
would be a good starting point.

   As far as the processing of the matrix, assuming there are
more than one of you, have one play dumb at a black board,
or a piece of paper, and have the rest walk through the algorithm
telling the victim what to do.  Write down pseudo-code (or a
computer language you are familar with) to map out your
program logic.  For example, use a grid of eight boxes for the
CPU registers.  And another grid for locations in memory.
Another grid of eight boxes for the FPU registers, if needed
(that would be rather advanced).  Write out a list of opcodes
that you are expected to use to help in telling someone what
to do.

   What programming environment are you using?  Do you
have a library of routines available?  For ASCII to binary number
conversion for instance.  What text book is the class using?

Regards,

Steve

[jj2007]

Jochen, he said each element of matrix is 8 bytes, not real 8.

Rui, I had seen that and guessed that it was binary data, so 8 bytes = real8. But (see recent posts) it could also be text.

Brett, the best way to get clarity about the format is to post a sample "database". Just zip it and attach it.

[RuiLoureiro]

and what to do with them

   Find the MATLAB documentation and find what format the
elements are stored in.  Real4 and integers are possible.

Thanks for the help so far.  The matrix elements in the input and output file are both stored as integers.  The max matrix size, as told by our instructor, will be 255x255.  Our code needs to be able to read the row and column inputs, decide which of the values is smaller so that the correct diagonal can be setup, then loop all the way through the matrix beneath the diagonal to zero-out the elements.

Also, the file format is 2 bytes (R & C) then all the elements separated by one space each.  i.e. R C (element) (element) (element) (element) (element) etc.

Hi brettc431,
                     I could help you but only and if only it was written in 32 bits
In this forum we may find "The calculator" that does matrix and you may find
also a library Math10 where you may find procedures to convert string to real and real to string. I already wrote code for matrix, all operations in real4, real8, real10, integer32 and integer64 but i need time to test all that work.
                   In "Campus" you can see the topic: "converting string to real4" and you can download the zip file. You will find a good procedure to convert string to real 4 in 32 bits
:icon14:

[brettc431]

I've got a partner working on the open, read, write, and close.  I'm working on the algorithm for reducing the matrix.

Here's what I've got so far but I don't know how to implement this into code:

Say the matrix is:

M    =    1   2   3   4
      5   6   7   9
      10   11   12   13


Algorithm for reducing the matrix:
1.    Determine the number of diagonal elements 

2.   Create a loop that goes through the diagonal elements

3.   Read a diagonal element M(I,I) and the one next to it. The one next to it will the next element in the row below it. Use M[d*8+2] to get the diagonal element. Save both into variables: e=M(I,I) and ep1=M(I+1,I).

E.g. the first diagonal element is M(1,1), d = (1-1)*3+1-1=0 => M(1,1)=M[0*8+2]=M[2]. Move the file pointer to 2. Read 8 bytes into variable e. Then read another 8 bytes in ep1.

We want to perform the row subtraction for an entire row starting with the element under the diagonal and ending with the last column of the row

Also, we must scale the row subtraction to give 0 underneath the diagonal. Scale = -e/ep1.

E.g. for M(1,1) = 1; M(2,1) = 5; scale = -1/5.

Set r= I+1 = 2, set c = I=1.
M(r,c) = M(r,c)*scale + M(I,I)       ;read M(r,c) by calculating M[8*d+2]
Write M(r,c) in the output file       ;requires that the output file be initialized.
c = c+1
Repeat until c = Col = 4.

What this would do is
   M(2,1)= 5(-1/5) + 1 = 0
   M(2,2)= 6(-1/5) + 2 = -4/8
   M(2,3)= 7(-1/5) + 3 = -8/5
   M(2,4)= 8(-1/5) + 4 = -12/5

By initialized output file, I mean that the output file is not blank. This can be done by copying the input file into the output, or writing zero's equivalent to the size of the input file into the output file.

4.   Make the diagonal M(I,I)=1. Divide the entire row of the diagonal by the value in the diagonal.
E.g. for the first diagonal element:
Set r=I=1, set c=I=1
   M(r,c) = M(r,c)/e         ; read M(r,c) by calculating M[8*d+2]
Write M(r,c) in the output file       ;requires that the output file be initialized.
c = c+1
Repeat until c = Col = 4.

Step 4 is carried out after step 3 because it will be faster that way.

5.   Loop to step 3.


Any help on the code itself?  Even just a basic format would be a help at this point.  The project has to be running by monday evening.

[dedndave]

I've got a partner working on the open, read, write, and close.  I'm working on the algorithm for reducing the matrix.

he got the better end of that deal - lol
(tell him to look up INT 21h, functions 3Ch, 3Dh, 3Eh, 3Fh, and 40h)

as Jochen mentioned....
http://masm32.com/board/index.php?topic=1813.msg18636#msg18636
it would make things easier if we could see an example database
that's not because of read and write
it's because we want to see the numeric format

[brettc431]

I'm not sure what you're asking for,  I am a total beginner to masm.

[dedndave]

what we would like to see is an example file from MATLAB
you can attach ZIP files to your post by clicking on the "Attachments and other options" link under the reply window

we need to see exactly how the values are stored in the file

[brettc431]

This is what the instructor sent us:

E.g. If the matrix is M = [
1.0 2.0 3.0
4.0 5.0 6.0
7.0 8.0 9.0]

Then input file will contain: 3,3,1.0,4.0,7.0,2.0,5.0,8.0,3.0,6.0,9.0

Note that the first 2 values are R and C, and the remaining values are the elements organized by columns. The values in hex will be:

03,03,3FF0000000000000,4010000000000000,401C000000000000,4000000000000000,4014000000000000,4020000000000000,4008000000000000,4018000000000000,4022000000000000

Matlab commands:
M = [1 2 3; 4 5 6; 7 8 9]; %creates a 3x3 matrix
[r c] = size(M);                %find size of M
mvec = reshape(M,1,r*c);         %converts matrix into a vector of columns
fid = fopen('inputfile','w')    %opens a file to store mvec into
fwrite(fid,[r c],'uint8')        %store the row and column a byte values
fwrite(fid,mvec, 'double')              %Store as double precision values
fclose(fid)                   %close file



We are to use the above MATLAB commands to create a matrix with random elements, then reduce it through masm.  I know it isn't a database, but I do not have MATLAB on my personal computer at home.

[dedndave]

that is probably enough info for us to work with   :t
assuming the values are stored in binary   :P

the row and column values are "unsigned byte integers"
the matrix values are "real8 floating point" format, also known as double precision

we can align the data by aligning to 4 or 8, then padding the buffer with 2 or 6 bytes to align the reals
i.e., read data to buffer+2 or buffer+6