The matrix calculator, module 3.21, provides a general tool which allows easy implementation of most types of matrix computations that are needed in the context of transportation planning.
Some specialized applications, however, require the evaluation
of a special class of matrix computations which cannot, or not easily,
be mapped onto the element-by-element operations performed by the
EMME/2 matrix calculator. These are usually models which imply, for
each O-D pair pq, the enumeration of a set of intermediate zones k.
The simplest example of an operation of this type is the
mathematical matrix multiplication 
, which corresponds
to the formula
While the above formula is mathematically well defined, it
has, as such, no immediate practical use in transportation planning.
Another problem of this type which does occur in practice is
finding the best parking lot k for a park&ride trip from p
to q, given the (weighted) auto and transit impedances 
and
. Assuming for the moment that the parking costs are the same
for all lots, this model can be expressed as
Note that the two formulae differ only in the operators used to combine
the elements of the two operand matrices ( 
vs. +) and the operators
used to contract the partial results over the range of intermediate zones
( 
vs. 
). The general class of this type of operations is
called matrix convolutions. The computation of such
a convolution implies a huge number of operations, i.e. O( 
) for
N zones (which means 1000'000'000 operations for a network having
1000 zones). Thus, for tackling this type of problem, a very efficient
implementation is extremely important. While it would be possible -at
least in principle- to compute such matrix convolution with a macro
which decomposes the problem by row or column and calls module 3.21
repeatedly, this would not be feasible from a practical point of view
for any but the smallest applications.
For this reason, a new module, 3.23 ``Matrix Convolutions'', has been added to EMME/2. This new module complements the standard matrix calculator 3.21 by providing a powerful tool to compute a wide range of matrix convolutions. While most users probably will have no direct need for evaluating matrix convolutions, this module will be most useful to those who do apply this kind of specialized models.
Important note: If you do not feel comfortable with mathematical formulations as those given above, chances are that you will never need to apply this new module directly, so you should not bother with the mathematical details that follow. (The new module might still prove useful to you for running macros developed by someone else.)
The general convolution formula which can be handled by the new module 3.23 is of the following form
where any valid binary operator can be chosen for the
matrix combination operator 
, as well as for the
contraction operator 
.
In addition to the simple convolution
formulae used in the examples above, module 3.23 allows up to 10 levels
of masking functions or operations, indicated above by
. Each of these masking levels can consist of
either an intrinsic function call (e.g. exp(...)) or a masking
operator and operand pair (e.g. (...+M)). The masking operands
can be either constants, origin or destination matrices, or, with some
limitations, full matrices (see User's Manual for details).
The subsets of origins, destinations and intermediate zones ( 
,
and 
) are definable by the usual zone subset selection
dialog. Also, a constraint matrix can be specified to define
the applicable O-D pairs pq.
If minimum or maximum is used as contraction operator (.min.
or .max.), it is possible to save the argmin/argmax results.
This is the matrix of zone indices 
which led to the minimum/maximum
result values.
Given the possible complexity of the convolution formulae, such a formula is not entered as an expression, but is defined by a dialog sequence in which the user defines the operand matrices, the combination and contraction operators, as well as any applicable masking functions, operators and operands. Once the convolution is defined in this manner, the system translates it into the corresponding formula, which is shown to the user, so that he can visually verify it.
As said before, for large applications, the CPU time used for the computations of convolutions can be considerable, as the number of operations grows with the third power of the number of zones. To illustrate this with times obtained on a SPARCstation IPX, the computation of a simple convolution over all origins, destinations and intermediate zones takes 6.4 seconds for the Winnipeg application, which has 154 zones. But the same convolution computed for the 850 zone Stockholm application takes already 19 minutes!
In the short time that this module has been available for testing, many interesting applications have already come up, including models for park&ride, activity based trip chaining, trip distribution based on intervening opportunities, as well as applications for aggregation/disaggregation or smoothing of demand matrices.
To illustrate the working of the new module 3.23, we return to the
park&ride example used at the beginning. Instead of selecting the
best parking lot by minimizing only the total auto and transit impedance,
we now shall include a additional term 
containing the parking cost
at lot k, weighted and converted into the appropriate impedance units.
This can be done by using one level of masking, using ``+'' as
masking operator and the destination matrix containing the parking costs
as masking operand. The following shows the dialog and the output report
generated by module 3.23 for this example:
3.23 MATRIX CONVOLUTIONS
Select: 1= compute matrix convolution
2= change module parameters
3= end
1
First operand matrix
Enter: Matrix=uAU
mf04: uAU auto impedances scenario 1000 (94-03-30 14:43)
Enter: Matrix combination operator (*)=+
Second operand matrix
Enter: Matrix=uTR
mf05: uTR transit impedances scenario 1000 (94-03-27 17:28)
Use transpose of second operand matrix? no
Enter: Masking operator/function 1 (optional)=+
Same masking value for all intermediate zones? no
Matrix containing masking value 1
Enter: Matrix=parkco
md02: parkco parking costs converted to imped. units (94-03-30 14:43)
Enter: Masking operator/function 2 (optional)=
Enter: Contraction operator (+)=.min.
Result matrix
Enter: Matrix( mf )=uPR
mf08: uPR minimum park&ride impedance (94-05-20 16:02)
Change header information? no
Matrix to hold argmin intermediate zones (optional)
Enter: Matrix( mf )=PRlot
mf09: PRlot intermediate zone for park&ride trips (94-05-18 15:10)
Change header information? no
Convolution formula:
mf08 = MIN (mf04 + mf05 ) + md02
pq k pk kq k
Submatrix? no
Constraint matrix
Enter: Matrix=
Computing matrix convolution:
Computation completed using 11.8 CPU seconds ( 310390 comb.ops/sec).
No. of result values: 23716
Minimum result value: 0.000000
Maximum result value: 63.601002
Average result value: 21.693945
Sum of result values: 514493.593750
Generate summary report? yes
Select: List device
1= Terminal
2= Printer
1
EMME/2 Module: 3.23 Date: 94-05-20 16:39 User: E001/H.SPIESS...HS
Project: EMME/2 STANDARD DEMONSTRATION AND TEST DATA BANK
---------------------------------------------------------------------------------------------------
COMPUTE MATRIX CONVOLUTION
**************************
Convolution formula:
mf08 = MIN (mf04 + mf05 ) + md02
pq k pk kq k
First operand matrix: mf04: uAU auto impedances scenario 1000 (94-03-30 14:43:16)
Matrix combination op.: +
Second operand matrix: mf05: uTR transit impedances scenario 1000 (94-03-27 17:28:31)
Masking operator 1: +
Masking value matrix 1: md02: parkco parking costs converted to imped. units (94-03-30 14:43:07)
Contraction operator: .min.
Result matrix: mf08: uPR minimum park&ride impedance (94-05-20 16:38:04)
Argmin result matrix: mf09: PRlot intermediate zone for park&ride trips (94-05-20 16:39:33)
Origin zones (p): all
Intermediate zones (k): all
Destination zones (q): all
No. of result values: 23716
Minimum result value: 0.000000
Maximum result value: 63.601002
Average result value: 21.693945
Sum of result values: 514493.593750
Computation time: 11.77 CPU seconds ( 310390 comb.ops/sec).