Matrix Trilogy [LONG]



#7

Hi ya all, specially HP-15C & RPN lovers:

A new week has begun, so there you are, a new, original HP-15C quiz/challenge I've composed and solved for you to sharpen
your RPN teeth. As always, though the actual solutions are particularized to the HP-15C,
the techniques featured can be useful for many other HP models (HP-71B/Math, HP-42S, HP-41/Advantage)
so you may want to have a go at it with said models as well; the intended solutions are
certainly rewritable for those models (I've done that for the 71B, actually).

The quiz's theme is as follows: comprehensive and well-designed as the HP-15C's matrix capabilities are, there are some
very useful functions that regrettably were not included in the instruction set.
For instance, there's no "SUM" function which will return the sum of all the elements
of a given matrix (!)

So, this week's quiz (kind of a trilogy, actually) centers around the missing "SUM" matrix
function, asking for a general solution and two particular cases, as follows:

1) Given an arbitrary MxN matrix, which contains arbitrary values (positive, negative
or zero), write a routine (LBL A, ..., RTN) which takes the matrix descriptor in the X-register
as input, and returns the sum of all the elements in the matrix. For instance:

      A =  |  3  -21  7  |  must return S = 3-21+7+2-10+8 = -11
| 2 -10 8 |
The routine must be primarily optimized for speed, and subject to that, be as short as
possible and consume the least resources (registers, labels, subroutine levels, flags, etc). We are only interested in the sum of the elements, not the matrix itself (which
for all we care, might be destroyed in the main program as soon as your routine has returned, to free RAM).

Under these conditions, there is a solution in 20 steps or less (LBL and RTN included),
which takes some 10 seconds to return the sum of all 60 elements of a 10x6 matrix.


2) Write an specialized routine for the particular case in which all the elements of the matrix
happen to be arbitrary sines and/or cosines [i.e.: values of sin(x) or cos(x)]. For instance:
(values obtained in radians, displayed in FIX 4)

      A = | sin(2)   sin(4)   sin(1)  |  must return S = -0.1033
| sin(6) sin(5) sin(3) |
(of course you don't have to evaluate any sin/cos, they
already come evaluated, you only have to add them up quickly).

For this special case, there is a solution in 13 steps or less (LBL-RTN included)
which takes some 5 seconds to return the sum of all 60 elements of a 10x6 matrix.


3) Write another specialized routine for the case in which all the elements of the matrix
happen to be arbitrary values of the exponential function [i.e.: values of e^x].
For instance (result displayed in FIX 4):

      A = | e^1.2  e^1.4  e^1.1  |  must return S = 23.4835
| e^1.6 e^1.5 e^1.3 |
For this particular case, there is a solution in 9 steps or less (LBL-RTN included)
which takes only 2.5 seconds to return the sum of all 60 elements of a 10x6 matrix.


That's all. Give it a fair try, it's quite an interesting, genuinely useful problem, and
I eagerly await for your own implementations and ideas (remember to test your routines against
the 2x3 numerical cases given, and to time their speed for a suitably filled-up 10x6 matrix).

Best regards :-)


Edited: 17 June 2003, 6:21 a.m.


#8

Once again, thanks Valentin for the opportunity to use the little grey cells.

For pedagogical reasons, I provide the answers to your questions in reverse order. I will also post separate messages for each question to allow the interested reader to pick up and continue the solution.

3) First, we consider a simpler case where the matrix consists of a single row. If you look at the instruction set of the HP-15C, you will find that [f][MATRIX][7] computes the matrix row norm. In the case of a one row matrix, this is almost what we want (i.e., the sum of values of the elements of the matrix). The difference is that the row norm takes the absolute values of the matrix elements first, before summing. However, in the restricted case of Valentin's question 3, this is not a problem: exponentials like e^1.2 are always positive. Putting this together, here is the solution to the problem for a one row, non-negative matrix:

001 LBL A
002 f MATRIX 7
003 RTN

Like, good thing the 15C is programmable, eh?

Well, consider now the more general case of a multi-row, but still positive, matrix. The solution here is not much harder: we simply re-dimension the matrix to have a single row! Of course, the sum of the matrix elements is not changed by the re-dimensioning operation, so here is the complete solution to Question 3:

001 LBL A
002 STO I
003 1 // = number of desired rows
004 RCL DIM I // X,Y = matrix dimensions
005 * // Total number of elements = number of desired columns
006 f DIM I // Re-dimension the matrix to have one row
007 RUP // Roll up the stack
008 f MATRIX 7 // Row norm = our answer
009 RTN

#9

Hi, Patrick & everyone following this thread:

Absolutely correct. My own original solution was as follows, with comments describing how it deals with

      A = | e^1.2  e^1.4  e^1.1  |  which must return S = 23.4835
| e^1.6 e^1.5 e^1.3 |
For this special case (all matrix elements are >= 0), there is a solution in 9 steps or less (LBL-RTN included) which takes only 2.5 seconds to return the sum of all 60 elements of a 10x6 matrix
        LBL A         begins routine. Say we've got 2x3 matrix above in the X-register
STO I for indirect addressing of the matrix
EEX 1 (EEX is slightly faster than 1 itself)
RCL DIM I recall matrix dimensions to X,Y: X -> 2, Y-> 3
* total number of elements = 2*3 = 6, Y holds 1
DIM I redimension the matrix to 1x6
RCL I recall the matrix descriptor to X
MATRIX 7 find the sum of the absolute values of all elements = 23.4835
RTN returns to the calling program

Of course, this works not only for values of e^x, but
for any other values as long as they all are >= 0.

Best regards.

#10

2) Now to answer Valentin's second question, where the matrix elements consist of the sines and cosines of various angles. Well, this type of matrix is no longer non-negative, so the technique we used in Part 1 does not apply directly. However, the essential attribute of sines and cosines is that they are never less than -1. So, if we were to add 1 to every element of the matrix, we would have a non-negative matrix again and the earlier technique could be used. Of course, we've changed the sum of the elements of the matrix by doing this, but in an entirely predictable way: we've added to the sum a number exactly equal to the number of elements in the matrix!

Here is a program which is based on this algorithm. It adds one to each element of the matrix, finds the row norm, then subtracts from that value the total number of matrix elements.

001 LBL A
002 STO I
003 1
004 RCL DIM I
005 *
006 f DIM I // redimension matrix to a single row
007 x<>I // put num elements into I, matrix into X
008 STO RESULT // prepare for matrix arithmetic
009 + // add one to matrix
010 f MATRIX 7 // calculate row norm
011 RCL - I // subtract num of matrix elements from total
012 RTN

#11

Hi, Patrick & everyone following this thread:

Again, absolutely correct. My own original solution was as follows, with comments describing how it deals with

      A = | sin(2)   sin(4)   sin(1)  |  which must return S = -0.1033
| sin(6) sin(5) sin(3) |
For this special case, there is a solution in 13 steps or less (LBL-RTN included)
which takes only 5 seconds to return the sum of all 60 elements of a 10x6 matrix.
        LBL A         begins routine. Say we've got 2x3 matrix above in the X-register
STO I for indirect addressing of the matrix
STO RESULT we'll operate on the matrix itself
EEX 1 (EEX is slightly faster than 1 itself)
- subtracting 1 from all elements makes them all negative or 0
EEX 1 (again, faster)
RCL DIM I recall matrix dimensions to X,Y: X -> 2, Y-> 3
* total number of elements = 2*3 = 6, Y holds 1
DIM I redimension the matrix to 1x6
RCL I recall the matrix descriptor to X, Y holds 6
MATRIX 7 find the sum of the absolute values of all elements = 6.1033
- subtracting it from 6 gives the result sum = 6-6.1033 = -0.1033
RTN returns to the calling program

As you may see, your solution is one step shorter (thanks to that nifty X<>I, RCL-I technique, though the byte count is the same, because RCL-I requires two bytes) but there is another difference: you add 1 to all elements in the matrix, to make them all positive or zero, while my solution subtracts 1 from all the elements in the matrix, to make them all negative or zero! :-)
In this particular case of sines and cosines, it doesn't matter at all, of course. Otherwise, your routine would work unchanged if all elements where >= -1 while mine would work unchanged if all elements where <= +1.

Of course, this works not only for values of sin(x), but for any other values as long as they all are <= 1 (for my solution, or >= -1 for yours). By changing it slightly, it will work as well whenever you know that your values are all of them less than some limit or all of them greater than some limit. The (very easy) details are left as an exercise for the reader. :-)

Best regards.

#12

1) Finally, to the general question that Valentin posed, his question number 1.

No longer do we have either a positive matrix, nor a matrix nicely bounded below so that we can easily make it positive ... or do we?

It is late here and I do not have the time to give the entire solution right now, so I encourage others to fill in the remainder of the solution. Here is a hint. We've seen what the row norm does for a matrix with a single row. What does it do for a matrix with a single column?

Good night for now and happy programming...


Possibly Related Threads...
Thread Author Replies Views Last Post
  AFTER HP-Prime update, Shift+Matrix CRASHES Joseph Ec 3 1,030 12-06-2013, 11:06 AM
Last Post: Joseph Ec
  HP Prime Matrix TERRIBLE bug and question uklo 19 2,604 11-25-2013, 12:10 PM
Last Post: Mic
  HP Prime: editing a matrix Alberto Candel 6 1,164 11-20-2013, 06:26 PM
Last Post: Helge Gabert
  Absolute Value and Matrix BruceTTT 5 1,088 11-11-2013, 11:52 PM
Last Post: Walter B
  HP Prime: Long integers (continued) Helge Gabert 2 734 11-07-2013, 11:24 AM
Last Post: Helge Gabert
  HP Prime: Pass "Long" Integers to a Program Helge Gabert 6 1,238 11-03-2013, 01:12 PM
Last Post: Helge Gabert
  HP Prime polynomial long division bluesun08 13 1,798 10-30-2013, 03:29 AM
Last Post: parisse
  WP-34S Matrix operations with routine-local registers? Tom Grydeland 1 600 09-04-2013, 10:46 AM
Last Post: Marcus von Cube, Germany
  SandMatrix Released - The trilogy is complete. Ángel Martin 3 876 08-30-2013, 05:35 PM
Last Post: Marcel Samek
  Matrix Characteristic Polynomial - Reloaded. Ángel Martin 12 1,675 08-22-2013, 05:33 PM
Last Post: Thomas Klemm

Forum Jump: