4.13 _JT_ storage_ CSS_ - column sequential format

• Status: IMPLEMENTED
• Current value: 12
• Also requires:

  Variable	Meaning	Value
  ia(_JT_ nunk_)	number of unknowns	2
  ia(_JT_ nelem_)	number of active elements	3

• Description:

  CSS format is another variation of COO format, similar to RSS. In this format the positions in the full matrix are numbered from 1 to ia(_JT_ nunk_) * ia(_JT_ nunk_) , starting with element (1,1), and proceeding down each column in succession to element (ia(_JT_ nunk_) ,ia(_JT_ nunk_) ). For example, the elements of a 3 x 3 matrix would be numbered as follows:

  A = $$\left(\vphantom{ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} }\right.$$$$\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}$$ $$\left.\vphantom{ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} }\right)$$     $$\Longrightarrow$$    $$\left(\vphantom{ \begin{array}{ccc} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{array} }\right.$$$$\begin{array}{ccc} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{array}$$ $$\left.\vphantom{ \begin{array}{ccc} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{array} }\right)$$

  So again a is a vector of length ia(_JT_ nelem_) containing the active elements of A. The map array ja is again a vector of length ia(_JT_ nelem_) containing the sequence number of the corresponding element of a, that is: $(j-1) * \mbox{\texttt{ia(}\textsf{\_JT\_ nunk\_}\texttt{)} \index{ia@\texttt{ia}! \_JT\_ nunk\_@\textsf{\_JT\_ nunk\_}}} + i$. The elements of a can be in any order, except that the main diagonal elements must be in the first ia(_JT_ nunk_) elements.

  Advantages:

  • stores no extra zero elements (unless you want to)
  • matrix-vector multiply implemented as single loop, so longer vector length
  • ja is half as long as with COO format

  Disadvantages:

  • indirect references plus significant integer arithmetic (including integer division) required
  • requires use of large integers (up to ia(_JT_ nunk_) * ia(_JT_ nunk_) ), which can lead to integer overflow for even moderate problem sizes (> $\sim$ 46,000 unknowns for 4-byte integers)

  Example:

  A = $$\left(\vphantom{ \begin{array}{ccccc} 11 & 0 & 0 & 14 & 15 \\ ... ...& 0 \\ 41 & 0 & 0 & 44 & 45 \\ 51 & 0 & 0 & 54 & 55 \end{array} }\right.$$$$\begin{array}{ccccc} 11 & 0 & 0 & 14 & 15 \\ 0 & 22 & 0 & 0 &... ...& 33 & 0 & 0 \\ 41 & 0 & 0 & 44 & 45 \\ 51 & 0 & 0 & 54 & 55 \end{array}$$ $$\left.\vphantom{ \begin{array}{ccccc} 11 & 0 & 0 & 14 & 15 \\ ... ...& 0 \\ 41 & 0 & 0 & 44 & 45 \\ 51 & 0 & 0 & 54 & 55 \end{array} }\right)$$

  could be represented in column sequential format by the arrays a and ja as:
  
  a = ( 11, 22, 33, 44, 55, 41, 51, 14, 54, 15, 45 )
  
  ja = ( 1, 7, 13, 19, 25, 4, 5, 16, 20, 21, 24 )