*****************************************************************************
*****************************************************************************
Buffer Issue Resolution Document (BIRD)
BIRD ID#: 29.2
ISSUE TITLE: Banded_matrix Extension
REQUESTOR: Bob Ross, Interconnectix, Inc.
DATE SUBMITTED: 26 May 1995, 5 June 1995
DATE ACCEPTED BY IBIS OPEN FORUM: 30 June 1995 (29.1), 21 July 1995 (29.2)
******************************************************************************
******************************************************************************
STATEMENT OF THE ISSUE:
In the Package Model description in IBIS Version 2.1, the Banded_matrix
format needs to be extended to remove a technical limitation.
******************************************************************************
STATEMENT OF THE RESOLVED SPECIFICATIONS:
The relevant portion of the original Specification is given along with
edited remarks or deletion comments are designate by "*" lines. BIRD29.2
changes are designate by "**" lines to add upper bound bandwidth limits.
 Banded_matrix

 A Banded_matrix is one whose entries are guaranteed to be zero if they
 are farther away from the main diagonal than a certain distance, known
 as the "bandwidth." Let the matrix size be N, and let the bandwidth
 be B. An entry [I,J] of the matrix is zero if:

  I  J  > B

 where . denotes the absolute value.

 The bandwidth for a Banded_matrix must be specified using the [Bandwidth]
 keyword:

==============================================================================
 Keyword: [Bandwidth]
 Required: Yes (for Banded_matrix matrices only)
 Description: Indicates the bandwidth of the matrix. The bandwidth field
 must be a nonnegative integer. This keyword must occur after
 the [Resistance Matrix], etc. keywords, and before the matrix
 data is given.
 Usage Rules:

[Bandwidth] 10

==============================================================================
 Specify the banded matrix one row at a time, starting with row 1 and
 working up to higher rows. Mark each row with the [Row] keyword, as
 above. As before, symmetry is exploited: do not provide entries below the
 main diagonal.

 The first row only needs to specify the entries [1,1] through [1,1+B] since
 any other entries are guaranteed to be zero. The second row will need to
 specify the entries [2,2] through [2, 2+B], and so on. In general, for row M
 the entries [M,M] through [M,M+B] are given.

 Unlike the Full_matrix, each successive row will typically have the same
 number of entries, except for the last few rows. When M + B finally exceeds
 the size of the matrix N, then the number of entries in each row starts to
 decrease; the last row (row N) has only 1 entry.

 As in the Full_matrix, if all the entries for a particular row do not fit
 into a single 80character line, the entries can be broken across several
 lines.

 It is possible to use a bandwidth of 0 to specify a diagonal matrix (a matrix
 with no coupling terms.) This is sometimes useful for resistance matrices.

**** Reword the Above Text with Changes Shown: *********************
 Banded_matrix

 A Banded_matrix is one whose entries are guaranteed to be zero if they
 are farther away from the main diagonal than a certain distance, known
* as the "bandwidth." Let the matrix size be N x M, and let the bandwidth
 be B. An entry [I,J] of the matrix is zero if:

  I  J  > B

 where . denotes the absolute value.
*
* The Banded_matrix is used to specify the coupling effects up to B pins
* on either side. Two variations are supported. One allows for the coupling
* to circle back on itself. This is technically a simple form of a bordered
* block diagonal matrix. However, its data can be completely specified in
* in terms of a Banded_matrix for an N x M matrix consisting of N rows
* and M = N + B columns. The second variation is just in terms of an N x N
* matrix where no circle back coupling needs to be specified.
*
 The bandwidth for a Banded_matrix must be specified using the [Bandwidth]
 keyword:

==============================================================================
 Keyword: [Bandwidth]
 Required: Yes (for Banded_matrix matrices only)
 Description: Indicates the bandwidth of the matrix. The bandwidth field
 must be a nonnegative integer. This keyword must occur after
 the [Resistance Matrix], etc. keywords, and before the matrix
 data is given.
 Usage Rules:

[Bandwidth] 10

==============================================================================
 Specify the banded matrix one row at a time, starting with row 1 and
 working up to higher rows. Mark each row with the [Row] keyword, as
 above. As before, symmetry is exploited: do not provide entries below the
 main diagonal.

* For case where coupling can circle back on itself, consider a matrix of
* N pins organized into N rows 1 ... N and M columms 1 ... N, 1 ... B.
 The first row only needs to specify the entries [1,1] through [1,1+B] since
* all other entries are guaranteed to be zero. The second row will need to
* specify the entries [2,2] through [2,2+B], and so on. For row K
* the entries [K,K] through [K,K+B] are given when K + B is less than or
* equal to the size of the matrix N. When K + B exceeds N, the entries in the
* last columns 1 ... B specify the coupling to the first rows. For row K, the
* entries [K,K] ... [K,N] [K,1] ... [K,R] are given where R =
** mod(K + B  1, N) + 1. All rows will contain B + 1 entries. To avoid
** redundant entries, the bandwidth is limited to B <= int((N  1) / 2).
*
* For the case where coupling does not circle back on itself, the process is
* modified. Only N columns need to be considered. When K + B finally exceeds
* the size of the matrix N, the number of entries in each row starts to
** decrease; the last row (row N) has only 1 entry. This construction
** constrains the bandwidth to B < N.

 As in the Full_matrix, if all the entries for a particular row do not fit
 into a single 80character line, the entries can be broken across several
 lines.

 It is possible to use a bandwidth of 0 to specify a diagonal matrix (a matrix
 with no coupling terms.) This is sometimes useful for resistance matrices.

****************************************************************************

 Sparse_matrix

 A Sparse_matrix is expected to consist mostly of zerovalued entries, except
 for a few nonzeros. Unlike the Banded_matrix, there is no restriction on
 where the nonzero entries can occur. This feature is useful in certain
 situations, such as for Pin Grid Arrays (PGAs.)

 As usual, symmetry can be exploited to reduce the amount of data by
 eliminating from the matrix any entries below the main diagonal.

 An N x N Sparse_matrix is specified one row at a time, starting with
 row 1 and continuing down to row N. Each new row is marked with [Row]
 keyword, as in the other matrix formats.

 Data for the entries of a row is given in a slightly different format,
 however. For the entry [I, J] of a row, it is necessary to explicitly
 list the name of pin J before the value of the entry is given. This
 specification serves to indicate to the parser where the entry is put into
 the matrix.

 The proper location is not otherwise obvious because of the lack of
 restrictions on where nonzeros can occur. Each (Index, Value) pair is
 listed upon a separate line. An example follows. Suppose that row 10
 has nonzero entries [10,10], [10,11], [10,15], and [10,25]. The
 following row data would be provided:

[Row] 10
 Index Value
10 5.7e9
11 1.1e9
15 1.1e9
25 1.1e9

 Note that each of the column indices listed for any row must be
 greater than or equal to the row index, because they always come from
 the upper half of the matrix. When alphanumeric pin names are used,
 special care must be taken to ensure that the ordering defined in the
 [Pin Numbers] section is observed.

 Also, note that it is again necessarily the case that the N'th
 row of an N x N matrix has just a single entry (the diagonal entry.)

**** Reword the Above Sentence: *******************************

* With this convention, please note that the N'th row of an
* N x N matrix has just a single entry (the diagonal entry).

****************************************************************
==============================================================================
******************************************************************************
ANALYSIS PATH/DATA THAT LED TO SPECIFICATION
In order to reduce the size of the symmetrical matricies, there are several
statements describing data entries only ON or ABOVE the main diagonal.
That was the intention of the bandedmatrix description. However the
format prevented entering the coupling between the last pins and the
first pins.
A simple 4pin example with a bandwidth of 1 illustrates the problem. The
"data" entries are the two digit subscripts of the matrix entries and are
shown using quote marks "".
Version 2.1 does not allow defining the coupling between pin 4 and 1:
[Inductance Matrix] Banded_matrix
[Bandwidth] 1
[Row] 1
"11" "12"
[Row] 2
"22" "23"
[Row] 3
"33" "34"
[Row] 4
"44"
One possible solution is to augment the Banded_matrix format for the
first rows by the entries that could not be entered in the last rows.
This would preserve the ABOVE the diagonal convention.
[Inductance Matrix] Banded_matrix
[Bandwidth] 1
[Row] 1
"11" "12" "14"
[Row] 2
"22" "23"
[Row] 3
"33" "34"
[Row] 4
"44"
However, the solution proposed here is to keep the number of columns the same
and to wrap around the entries for the last rows as needed. Technically
the entries are BELOW the main diagonal. The "41" entry would really be
entered as "14" in the reduced uppertriangle matrix data structure.
[Inductance Matrix] Banded_matrix
[Bandwidth] 1
[Row] 1
"11" "12"
[Row] 2
"22" "23"
[Row] 3
"33" "34"
[Row] 4
"44" "41"
BIRD29.1 provides another way looking at the formating. The "41" entry can
now be viewed as an uppertriangle entry of the original matrix augmented
by repeating columns 1 ... B. Using symmetry, this format gives all of
the information needed to describe all coupling by the B adjacent pins.
Commentors on BIRD29 discussed nomenclature (banded, bandwidth, bordered block
diagonal matrix) and proposed other terms. One concern was whether to retain
the existing definition and add another term (such as Augmented_matrix) to
handle the wrap around situation. The revised data entry format can still be
referred to as banded when the first N columns are augmented by repeating
existing columns 1 ... B.
For compatibility reasons, support of the existing Banded_matrix format was
desireable. The proposed new format was only a slight variation on the
existing format, so it did not seem appropriate to introduce new nomenclature
for the change. The solution proposed in BIRD29.1 is to accept simutaneously
both format options. The intent is allow the technically robust functionality
within the existing nomenclature, and to allow the technically limited
descriptions be supported where wrap around coupling is of no concern. This
works because the terms missing in the existing format are zero in the more
robust format. The old format should be phased out rather than endorsed by
separate notation which must be supported indefinitely because it would allow
technically incomplete package model libraries.
This is a compromise position between those who would like the original
format definition deleted and those who would like to see both formats
supported using different terminology. The parser definition will be
overloaded, but for this situation, this is not a significant complication.
This problem does not occur in the Sparse_matrix format. So the restriction
text has a minor change in that portion of the Specification.
BIRD29.2 is issued to explicitly put in bandwidth limits. This is
in response to an IBISCHK2 question raised by Ron Neville regarding how
to treat redundant Banded_matrix entries when the entries are different.
******************************************************************************
ANY OTHER BACKGROUND INFORMATION