datastruct.tex

\section{Data Structures and Classes}
\label{sec:datastruct}
%\ifthenelse{\boolean{mtc}}{\minitoc}{}

In this chapter we  illustrate the  data structures used for definition of
routines interfaces. They  include data structures for sparse matrices,
communication descriptors and preconditioners.%%  These data structures
%% are used for calling PSBLAS routines in Fortran~90 language and will
%% be used to next chapters containing these callings.  

All the data types and the basic subroutine interfaces related to
descriptors and sparse matrices are defined in
the module \fortinline|psb_base_mod|; this will have to be included by every
user subroutine that makes use of the library. The preconditioners are
defined in the module \fortinline|psb_prec_mod|

Integer, real and complex data types are parametrized with a kind type
defined in the library as follows: 
\begin{description}
\item[psb\_spk\_] Kind parameter for short precision real and complex
  data; corresponds to a \fortinline|REAL| declaration and is
  normally 4 bytes; 
\item[psb\_dpk\_] Kind parameter for long precision real and complex
  data; corresponds to a \fortinline|DOUBLE PRECISION| declaration and is
  normally 8 bytes;
\item[psb\_mpk\_] Kind parameter for 4-bytes integer data, as is
  always used by MPI; 
\item[psb\_epk\_] Kind parameter for 8-bytes integer data, as is
  always used by the \fortinline|sizeof| methods;
\item[psb\_ipk\_] Kind parameter for ``local'' integer indices and data;
  with default build options this is a 4 bytes integer;
\item[psb\_lpk\_] Kind parameter for ``global'' integer indices and data;
  with default build options this is an 8 bytes integer;
\end{description}
The integer kinds for local and global indices can be chosen at
configure time to hold 4 or 8 bytes, with the global indices at least
as large as the local ones. 
Together with the classes attributes we also discuss their
methods.  Most methods detailed here only act on the local variable,
i.e. their action is purely local and asynchronous unless otherwise
stated. 
The list of methods here is not completely exhaustive; many methods,
especially those that alter the contents of the various objects, are
usually not needed by the end-user, and therefore are described in the
developer's documentation. 


\subsection{Descriptor data structure}
\label{sec:desc}
All the general matrix informations and elements to be
exchanged among processes are stored within a data structure of the
type \hypertarget{descdata}{{\tt psb\_desc\_type}}. 
Every structure of this type is associated with a discretization
pattern and enables data communications and other operations that are
necessary for implementing the various algorithms of interest to us. 

The data structure itself \fortinline|psb_desc_type| can be treated as an
opaque object handled via the   tools routines of
Sec.~\ref{sec:toolsrout} or the query routines detailed below;
nevertheless we include here a  description for the curious 
reader. 

First we describe the \fortinline|psb_indx_map| type. This is a data
structure that keeps track of a certain number of basic issues such
as:
\begin{itemize}
\item The value of the communication context;
\item The number of indices in the index space, i.e. global number of
  rows and columns of a sparse matrix;
\item The local set of indices, including:
\begin{itemize}
\item The number of local indices (and local rows);
\item The number of halo indices (and therefore local columns); 
\item The global indices corresponding to the local ones. 
\end{itemize}
\end{itemize}
There are many different schemes for storing these data; therefore
there are a number of types extending the base one, and the descriptor
structure holds a polymorphic object whose dynamic type can be any of
the extended  types. 
The methods associated with this data type answer the following
queries:
\begin{itemize}
\item For a given set of local indices, find the corresponding indices
  in the global numbering;
\item For a given set of global indices, find the corresponding
  indices in the local numbering, if any, or return an invalid 
\item Add a global index to the set of halo indices;
\item Find the process  owner of each member of a set of global
  indices.
\end{itemize}
All methods but the last are purely local; the last method potentially
requires communication among processes, and thus is a synchronous
method. The choice of a specific dynamic type for the index map is
made at the time the descriptor is initially allocated, according to
the mode of initialization (see also~\ref{sec:toolsrout}).

The descriptor contents are as follows:
\begin{description}
\item[{\bf indxmap}] A polymorphic variable of a type that is any
  extension of the indx\_map type described above. \\
\item[{\bf halo\_index}] A list of the halo and boundary elements for
the current process to be exchanged with other processes; for each
processes with which it is necessary to communicate:
\begin{enumerate}
\item Process identifier;
\item Number of points to be received;
\item Indices of points to be received;
\item Number of points to be sent;
\item Indices of points to be sent;
\end{enumerate}
% The list may contain an arbitrary number of groups; its end is marked
% by a -1.\\
Specified as: a vector of integer type, see~\ref{sec:vecttype}.
\item[{\bf ext\_index}] A list of element indices to be exchanged to
  implement the mapping between a base descriptor and a descriptor
  with overlap. \\
Specified as: a vector of integer type, see~\ref{sec:vecttype}.
\item [{\bf ovrlap\_index}] A list of the overlap elements for the
current process, organized in groups like the previous vector:
\begin{enumerate}
\item Process identifier;
\item Number of points to be received;
\item Indices of points to be received;
\item Number of points to be sent;
\item Indices of points to be sent;
\end{enumerate}
% The list may contain an arbitrary number of groups; its end is marked
% by a -1.\\
Specified as: a vector of integer type, see~\ref{sec:vecttype}.
\item [{\bf ovr\_mst\_idx}] A list to retrieve the value of each
  overlap element from the respective master process.\\
Specified as: a vector of integer type, see~\ref{sec:vecttype}.
\item [{\bf ovrlap\_elem}] For all overlap points belonging to th
ecurrent process:
\begin{enumerate}
\item Overlap point index;
\item Number of processes sharing that overlap points;
\item Index of a ``master'' process: 
\end{enumerate}
Specified as: an allocatable integer array of rank two.
\item [{\bf bnd\_elem}] A list of all boundary points, i.e. points
  that have a connection with other processes.
\end{description}
The Fortran~2003 declaration  for \fortinline|psb_desc_type| structures is 
as follows:
\begin{listing}[h!]
  % \begin{Sbox}
\ifpdf
\begin{minted}[breaklines=true,bgcolor=bg,fontsize=\small]{fortran}
type psb_desc_type 
    class(psb_indx_map), allocatable :: indxmap
    type(psb_i_vect_type) :: v_halo_index
    type(psb_i_vect_type) :: v_ext_index
    type(psb_i_vect_type) :: v_ovrlap_index
    type(psb_i_vect_type) :: v_ovr_mst_idx 
    integer, allocatable  :: ovrlap_elem(:,:)
    integer, allocatable  :: bnd_elem(:)
end type psb_desc_type 
\end{minted}
\else
\begin{center}
    \begin{minipage}[tl]{0.9\textwidth}
\begin{verbatim} 
type psb_desc_type 
    class(psb_indx_map), allocatable :: indxmap
    type(psb_i_vect_type) :: v_halo_index
    type(psb_i_vect_type) :: v_ext_index
    type(psb_i_vect_type) :: v_ovrlap_index
    type(psb_i_vect_type) :: v_ovr_mst_idx 
    integer, allocatable  :: ovrlap_elem(:,:)
    integer, allocatable  :: bnd_elem(:)
end type psb_desc_type 
\end{verbatim}
    \end{minipage}
  \end{center}
\fi
% \end{Sbox}
%   \setlength{\fboxsep}{8pt}
%   \begin{center}
%     \fbox{\TheSbox}
%   \end{center}
  \caption{\label{fig:desctype}The PSBLAS defined data type that
    contains the communication descriptor.}
\end{listing}
A communication descriptor associated with a sparse  matrix has a
state, which can take the following values:
\begin{description}
\item[Build:] State entered after the first allocation, and before the
  first assembly; in this state it is possible to add communication
  requirements among different processes. 
\item[Assembled:] State entered after the assembly; computations using
  the associated sparse matrix, such as matrix-vector products, are
  only possible   in this state.
\end{description}

\subsubsection{Descriptor Methods} 

\subsubsection{get\_local\_rows --- Get number of local rows}

\begin{verbatim}
nr = desc%get_local_rows()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of local rows, i.e. the number of
  rows owned by the current process; as explained in~\ref{sec:intro},
  it is equal to $|{\cal I}_i| + |{\cal B}_i|$. The returned value is
  specific to the calling process. 
\end{description}


\subsubsection{get\_local\_cols --- Get number of local cols}

\begin{verbatim}
nc = desc%get_local_cols()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of local cols, i.e. the number of
  indices used by the current process, including both local and halo
  indices; as explained in~\ref{sec:intro}, 
  it is equal to  $|{\cal I}_i| + |{\cal B}_i| +|{\cal H}_i|$. The
  returned value is specific to the calling process. 
\end{description}


\subsubsection{get\_global\_rows --- Get number of global rows}

\begin{verbatim}
nr = desc%get_global_rows()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of global rows, i.e. the size of the
  global index space. 
\end{description}

\subsubsection{get\_global\_cols --- Get number of global cols}

\begin{verbatim}
nr = desc%get_global_cols()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of global cols; usually this is equal
  to the number of global rows. 
\end{description}


\subsubsection{get\_global\_indices --- Get vector of global indices}

\begin{verbatim}
myidx = desc%get_global_indices([owned])
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
Type: {\bf required}.\\
\item[owned] Choose if you only want owned indices
  (\fortinline|owned=.true.|) or also halo indices (\fortinline|owned=.false.|). 
Scope: {\bf local}.\\
Type: {\bf optional}; default: \fortinline|.true.|.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The global indices, returned as an allocatable
  integer array of kind \fortinline|psb_lpk_|  and rank 1. 
\end{description}



\subsubsection{get\_context --- Get communication context}

\begin{verbatim}
ctxt = desc%get_context()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The communication context.
\end{description}

\subsubsection{Clone --- clone current object}

\begin{verbatim}
call  desc%clone(descout,info)
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[descout] A copy of the input object.
\item[info] Return code. 
\end{description}


\subsubsection{CNV --- convert internal storage format}

\begin{verbatim}
call  desc%cnv(mold)
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[desc] the communication descriptor.\\
Scope: {\bf local}.\\
\item[mold] the desired integer storage format.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
Specified as: a object of type derived from (integer) \vbasedata.
\end{description}
The \fortinline|mold|  arguments may be
employed to interface with special devices, such as GPUs and other
accelerators. 



\subsubsection{psb\_cd\_get\_hash\_threshold --- Get threshold for
  index mapping switch}

\begin{verbatim}
ith = psb_cd_get_hash_threshold()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Return]
\item[Function value] The current value for the size threshold. 

\end{description}



\subsubsection{psb\_cd\_set\_hash\_threshold --- Set threshold for
  index mapping switch}
%\addcontentsline{toc}{paragraph}{psb\_cd\_set\_large\_threshold}

\begin{verbatim}
call psb_cd_set_hash_threshold(ith)
\end{verbatim}

\begin{description}
\item[Type:] Synchronous.
\item[\bf On Entry]
\item[ith] the new threshold for communication descriptors.\\
Scope: {\bf global}.\\
Type: {\bf required}.\\
Intent: {\bf in}.\\
Specified as: an integer value greater than zero.
\end{description}
This threshold guides the library into using a list based or a
hash-table based descriptor for global to local index conversion;
if the size of the global index space is below this threshold, a list
based structure is used, if it is above a hash-table based structure
is used. 
Note: the threshold value is only queried by the library at the time a
call to \fortinline|psb_cdall| is executed, therefore changing the threshold
has no effect on communication descriptors that have already been
initialized. Moreover the threshold must have the same value on all
processes. 


\subsubsection{get\_p\_adjcncy --- Get process adjacency list}
%\addcontentsline{toc}{paragraph}{get\_p\_adjcncy}

\begin{verbatim}
list =  desc%get_p_adjcncy()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Return]
\item[Function value] The current list of adjacent processes,
  i.e. processes with which the current one has to exchange halo
  data. 

\end{description}

\subsubsection{set\_p\_adjcncy --- Set process adjacency list}
%\addcontentsline{toc}{paragraph}{set\_p\_adjcncy}

\begin{verbatim}
call desc%set_p_adjcncy(list)
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[list] the list of adjacent processes.\\
Scope: {\bf local}.\\
Type: {\bf required}.\\
Intent: {\bf in}.\\
Specified as: a one-dimensional array of integers of kind \fortinline|psb_ipk_|. 
\end{description}
Note: this method can be called after a call  to \fortinline|psb_cdall| and
before a call to \fortinline|psb_cdasb|. The user is specifying here some
knowledge about which processes are topological neighbours of the
current process. The availability of this information may speed up the
execution of the assembly call \fortinline|psb_cdasb|. 


\subsubsection{fnd\_owner --- Find the owner process of a set of indices}
%\addcontentsline{toc}{paragraph}{fnd\_owner}

\begin{verbatim}
call desc%fnd_owner(idx,iprc,info)
\end{verbatim}

\begin{description}
\item[Type:] Synchronous.
\item[\bf On Entry]
\item[idx] the list of global indices for which we need the owning processes.\\
Scope: {\bf local}.\\
Type: {\bf required}.\\
Intent: {\bf in}.\\
Specified as: a one-dimensional array of integers of kind \fortinline|psb_lpk_|. 
\item[\bf On Return]
\item[iprc] the list of processes owning the indices in \fortinline|idx|.\\
Scope: {\bf local}.\\
Type: {\bf required}.\\
Intent: {\bf in}.\\
Specified as: an allocatable one-dimensional array of integers of kind \fortinline|psb_ipk_|. 
\end{description}
Note: this method may or may not actually require communications, depending on
the exact internal data storage; given that the choice of storage may
be altered by runtime parameters, it is necessary for safety that this
method is called by all processes. 




\subsubsection{Named Constants}
\label{sec:cd_constants}
\begin{description}
\item[psb\_none\_] Generic no-op;
\item[psb\_root\_] Default root process for broadcast and scatter operations;
\item[psb\_nohalo\_]  Do not fetch halo elements;
\item[psb\_halo\_]  Fetch halo elements from neighbouring processes;
\item[psb\_sum\_] Sum overlapped elements
\item[psb\_avg\_] Average overlapped elements
\item[psb\_comm\_halo\_] Exchange data based on the \fortinline|halo_index|
  list;
\item[psb\_comm\_ext\_] Exchange data based on the \fortinline|ext_index|
  list;
\item[psb\_comm\_ovr\_] Exchange data based on the \fortinline|ovrlap_index|
  list;
\item[psb\_comm\_mov\_] Exchange data based on the \fortinline|ovr_mst_idx|
  list;

%% \item[psb\_square\_root\_] Update with the square root of the average
%%   of overlapped elements;
%% \item[psb\_dec\_type\_] Entry holding decomposition type (in \fortinline|desc_a%matrix_data|)
%% \item[psb\_m\_] Entry holding total number of rows
%% \item[psb\_n\_] Entry holding total number of columns
%% \item[ psb\_n\_row\_] Entry holding the number of rows stored in the
%%   current process
%% \item[psb\_n\_col\_] Entry holding the number of columns stored in the
%%   current process
%% \item[psb\_ctxt\_] Entry holding a copy of the BLACS communication context
%% \item[psb\_desc\_asb\_] State of the descriptor: assembled,
%%       i.e. suitable for computational tasks. 
%% \item[psb\_desc\_bld\_] State of the descriptor: build, must be
%%   assembled before computational use.
\end{description}


\subsection{Sparse Matrix class}
\label{sec:spmat}
The \hypertarget{spdata}{{\tt psb\_Tspmat\_type}} class
contains all information about the local portion of the sparse matrix and   
its storage mode. Its design is 
based on the STATE design pattern~\cite{DesignPatterns} as detailed
in~\cite{Sparse03}; the type declaration is shown in
figure~\ref{fig:spmattype} where \fortinline|T| is a placeholder for the
data type and precision variants 
\begin{description}
\item[S] Single precision real;
\item[D] Double precision real;
\item[C] Single precision complex;
\item[Z] Double precision complex;
\item[LS,LD,LC,LZ] Same numeric type as above, but with
  \fortinline|psb_lpk_| integer indices.
\end{description}
The actual data is contained in the polymorphic component \fortinline|a%a|
of type  \hypertarget{spbasedata}{{\tt psb\_T\_base\_sparse\_mat}}; its
specific layout can be chosen dynamically among the predefined types,
or an entirely new storage layout can be implemented and passed to the
library at runtime via the \fortinline|psb_spasb| routine. 
\begin{listing}[h!]
\ifpdf
\begin{minted}[breaklines=true,bgcolor=bg,fontsize=\small]{fortran}
  type :: psb_Tspmat_type
    class(psb_T_base_sparse_mat), allocatable  :: a 
  end type  psb_Tspmat_type
\end{minted}
\else
  % \begin{Sbox}
\begin{center}
    \begin{minipage}[tl]{0.85\textwidth}
\begin{verbatim}
  type :: psb_Tspmat_type
    class(psb_T_base_sparse_mat), allocatable  :: a 
  end type  psb_Tspmat_type
\end{verbatim}
    \end{minipage}
  \end{center}
% \end{Sbox}
%   \setlength{\fboxsep}{8pt}
%   \begin{center}
%     \fbox{\TheSbox}
%   \end{center}
\fi
  \caption{\label{fig:spmattype} 
    The PSBLAS defined data type that
    contains a sparse matrix.} 
\end{listing}
The following very common formats are precompiled in  PSBLAS and thus
are always available: 
\begin{description}
\item[psb\_T\_coo\_sparse\_mat] Coordinate storage; 
\item[psb\_T\_csr\_sparse\_mat] Compressed storage by rows; 
\item[psb\_T\_csc\_sparse\_mat] Compressed storage by columns; 
\end{description}
The inner sparse matrix has an associated state, which can take the
following values:
\begin{description}
\item[Build:] State entered after the first allocation, and before the
  first assembly; in this state it is possible to add nonzero entries.
\item[Assembled:] State entered after the assembly; computations using
  the sparse matrix, such as matrix-vector products, are only possible
  in this state;
\item[Update:] State entered after a reinitalization; this is used to
  handle applications in which the same sparsity pattern is used
  multiple times with different coefficients. In this state it is only
  possible to enter coefficients for already existing nonzero entries.
\end{description}
The only storage variant supporting the build state is COO; all other
variants are obtained by conversion to/from it. 

\subsubsection{Sparse Matrix Methods}

\subsubsection{get\_nrows --- Get number of  rows in a sparse  matrix}
%\addcontentsline{toc}{paragraph}{get\_nrows}

\begin{verbatim}
nr = a%get_nrows()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of  rows  of sparse matrix \fortinline|a|.
\end{description}


\subsubsection{get\_ncols --- Get number of  columns in a  sparse
  matrix}
%\addcontentsline{toc}{paragraph}{get\_ncols}

\begin{verbatim}
nc = a%get_ncols()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of  columns  of sparse matrix \fortinline|a|.
\end{description}


\subsubsection{get\_nnzeros --- Get number of nonzero elements
  in a sparse matrix}
%\addcontentsline{toc}{paragraph}{get\_nnzeros}

\begin{verbatim}
nz = a%get_nnzeros()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of nonzero elements stored in sparse matrix \fortinline|a|.
\end{description}

{\par\noindent\bfseries Notes}
\begin{enumerate}
\item The function value is specific to the storage format of matrix
  \fortinline|a|; some storage formats employ padding, thus the returned
  value for the same matrix may be different for different storage choices.
\end{enumerate}

\subsubsection{get\_size  --- Get maximum number of nonzero elements
  in a sparse matrix}
%\addcontentsline{toc}{paragraph}{get\_size }

\begin{verbatim}
maxnz = a%get_size()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The maximum number of nonzero elements that can
  be stored in sparse matrix \fortinline|a| using its current memory allocation.
\end{description}

\subsubsection{sizeof  --- Get memory occupation in bytes
of  a sparse matrix}
%\addcontentsline{toc}{paragraph}{sizeof }

\begin{verbatim}
memory_size = a%sizeof()
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The memory occupation in bytes.
\end{description}


\subsubsection{get\_fmt  --- Short description of the dynamic type}
%\addcontentsline{toc}{paragraph}{get\_fmt }


\fortinline|write(*,*) a%get_fmt()|


\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] A short string describing the dynamic type of
  the matrix. Predefined values include \fortinline|NULL|, \fortinline|COO|,
  \fortinline|CSR| and \fortinline|CSC|. 
\end{description}

\subsubsection{is\_bld, is\_upd, is\_asb  --- Status check}
%\addcontentsline{toc}{paragraph}{is\_bld, is\_upd, is\_asb }


\fortinline|if (a%is_bld()) then|\\
\fortinline|if (a%is_upd()) then|\\
\fortinline|if (a%is_asb()) then|

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] A \fortinline|logical| value indicating whether the
  matrix is in the Build, Update or Assembled state, respectively. 
\end{description}

\subsubsection{is\_lower, is\_upper, is\_triangle, is\_unit  ---
  Format  check}
%\addcontentsline{toc}{paragraph}{is\_lower, is\_upper, is\_triangle, is\_unit}

\ifpdf
\begin{minted}{fortran}
if (a%is_triangle()) then 
if (a%is_upper()) then 
if (a%is_lower()) then 
if (a%is_unit()) then 
\end{minted}
\else
\begin{verbatim}
if (a%is_triangle()) then 
if (a%is_upper()) then 
if (a%is_lower()) then 
if (a%is_unit()) then 
\end{verbatim}
\fi

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] A \fortinline|logical| value indicating whether the
  matrix is triangular; if \fortinline|is_triangle()| returns \fortinline|.true.|
  check also if it is lower, upper and with a unit (i.e. assumed)
  diagonal. 
\end{description}


\subsubsection{cscnv --- Convert to a different storage format}
%\addcontentsline{toc}{paragraph}{cscnv}

\ifpdf
\begin{minted}{fortran}
call  a%cscnv(b,info [, type, mold, dupl])
call  a%cscnv(info [, type, mold, dupl])
\end{minted}
\else
\begin{verbatim}
call  a%cscnv(b,info [, type, mold, dupl])
call  a%cscnv(info [, type, mold, dupl])
\end{verbatim}
\fi

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\item[type] a string requesting a new format.\\
Type: optional.
\item[mold] a variable of \fortinline|class(psb_T_base_sparse_mat)|  requesting a new format.\\
Type: optional.
\item[dupl] an integer value specifing how to handle duplicates (see
  Named Constants below)
\end{description}

\begin{description}
\item[\bf On Return]
\item[b,a] A copy  of \fortinline|a| with a new storage format.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[info] Return code. 
\end{description}
The \fortinline|mold|  arguments may be
employed to interface with special devices, such as GPUs and other
accelerators. 


\subsubsection{csclip --- Reduce to a submatrix}
%\addcontentsline{toc}{paragraph}{csclip}

\ifpdf
\begin{minted}{fortran}
    call a%csclip(b,info[,&
       & imin,imax,jmin,jmax,rscale,cscale])
\end{minted}
\else
\begin{verbatim}
    call a%csclip(b,info[,&
       & imin,imax,jmin,jmax,rscale,cscale])
\end{verbatim}
\fi

Returns the submatrix \fortinline|A(imin:imax,jmin:jmax)|, optionally
rescaling row/col indices to the range
\fortinline|1:imax-imin+1,1:jmax-jmin+1|.  
\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\item[imin,imax,jmin,jmax] Minimum and maximum row and column indices.\\
Type: optional.
\item[rscale,cscale] Whether to rescale row/column indices.
Type: optional.
\end{description}
\begin{description}
\item[\bf On Return]
\item[b] A copy  of a submatrix of \fortinline|a|.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[info] Return code. 
\end{description}

\subsubsection{clean\_zeros --- Eliminate zero coefficients}
%\addcontentsline{toc}{paragraph}{clean\_zeros}
\fortinline|call a%clean_zeros(info)|

Eliminates zero coefficients explicitly stored in the input matrix.  

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\end{description}
\begin{description}
\item[\bf On Return]
\item[a] The matrix  \fortinline|a| without zero coefficients.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[info] Return code. 
\end{description}
{\par\noindent\bfseries Notes}
\begin{enumerate}
\item Depending on the internal storage format, there may still be some amount of 
  zero padding in the output.
\item Any explicit zeros on the main diagonal are always kept in the
  data structure. 
\end{enumerate}

\subsubsection{get\_diag --- Get main diagonal}
%\addcontentsline{toc}{paragraph}{get\_diag}
\fortinline|call a%get_diag(d,info)|

Returns a copy of  the main diagonal.
\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\end{description}
\begin{description}
\item[\bf On Return]
\item[d] A copy  of the main diagonal.\\
A one-dimensional array of the appropriate type.
\item[info] Return code. 
\end{description}


\subsubsection{clip\_diag --- Cut out main diagonal}
%\addcontentsline{toc}{paragraph}{clip\_diag}
\fortinline|call a%clip_diag(b,info)|

Returns a copy of \fortinline|a| without the main diagonal.
\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\end{description}
\begin{description}
\item[\bf On Return]
\item[b] A copy  of  \fortinline|a| without the main diagonal.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[info] Return code. 
\end{description}


\subsubsection{tril --- Return the lower triangle}
%\addcontentsline{toc}{paragraph}{tril}

\ifpdf
\begin{minted}{fortran}
    call a%tril(l,info[,&
       & diag,imin,imax,jmin,jmax,rscale,cscale,u])
\end{minted}
\else
\begin{verbatim}
    call a%tril(l,info[,&
       & diag,imin,imax,jmin,jmax,rscale,cscale,u])
\end{verbatim}
\fi 

Returns the lower triangular part of submatrix
\fortinline|A(imin:imax,jmin:jmax)|, optionally rescaling row/col indices to
the range \fortinline|1:imax-imin+1,1:jmax-jmin+1| and returing the
complementary upper triangle. 
\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\item[diag] Include diagonals up to this one; \fortinline|diag=1| means the
  first superdiagonal, \fortinline|diag=-1| means the first subdiagonal. 
Default 0.
\item[imin,imax,jmin,jmax] Minimum and maximum row and column indices.\\
Type: optional.
\item[rscale,cscale] Whether to rescale row/column indices.
Type: optional.
\end{description}
\begin{description}
\item[\bf On Return]
\item[l] A copy  of the lower triangle of \fortinline|a|.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[u] (optional) A copy  of the upper triangle of \fortinline|a|.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[info] Return code. 
\end{description}

\subsubsection{triu --- Return the upper triangle}
%\addcontentsline{toc}{paragraph}{triu}
\ifpdf
\begin{minted}{fortran}
    call a%triu(u,info[,&
       & diag,imin,imax,jmin,jmax,rscale,cscale,l])
\end{minted}
\else
\begin{verbatim}
    call a%triu(u,info[,&
       & diag,imin,imax,jmin,jmax,rscale,cscale,l])
\end{verbatim}
\fi

Returns the upper triangular part of submatrix
\fortinline|A(imin:imax,jmin:jmax)|, optionally rescaling row/col indices to
the range \fortinline|1:imax-imin+1,1:jmax-jmin+1|, and returing the
complementary lower triangle. 
\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
A variable of type \fortinline|psb_Tspmat_type|.\\
Scope: {\bf local}.\\
\item[diag] Include diagonals up to this one; \fortinline|diag=1| means the
  first superdiagonal, \fortinline|diag=-1| means the first subdiagonal. 
Default 0.
\item[imin,imax,jmin,jmax] Minimum and maximum row and column indices.\\
Type: optional.
\item[rscale,cscale] Whether to rescale row/column indices.
Type: optional.
\end{description}
\begin{description}
\item[\bf On Return]
\item[u]  A copy  of the upper triangle of \fortinline|a|.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[l] (optional) A copy  of the lower triangle of \fortinline|a|.\\
A variable of type \fortinline|psb_Tspmat_type|.
\item[info] Return code. 
\end{description}




\subsubsection{psb\_set\_mat\_default --- Set default  storage format}
%\addcontentsline{toc}{paragraph}{psb\_set\_mat\_default}


\fortinline|call  psb_set_mat_default(a)|

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] a variable of \fortinline|class(psb_T_base_sparse_mat)|  requesting
  a new default storage format.\\ 
Type: required.
\end{description}





\subsubsection{clone --- Clone current object}
%\addcontentsline{toc}{paragraph}{clone}

\fortinline|call  a%clone(b,info)|

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[a] the sparse matrix.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[b] A copy of the input object.
\item[info] Return code. 
\end{description}


\subsubsection{Named Constants}
\label{sec:sp_constants}
\begin{description}
%% \item[psb\_nztotreq\_] Request to fetch the total number of nonzeroes
%%   stored in a sparse matrix
%% \item[psb\_nzrowreq\_] Request to fetch the number of nonzeroes in a
%%   given row in a sparse matrix
\item[psb\_dupl\_ovwrt\_] Duplicate coefficients should be overwritten
  (i.e. ignore duplications)
\item[psb\_dupl\_add\_] Duplicate coefficients should be added;	         
\item[psb\_dupl\_err\_] Duplicate coefficients should trigger an error conditino
\item[psb\_upd\_dflt\_] Default update strategy for matrix coefficients;
\item[psb\_upd\_srch\_] Update strategy based on search into the data structure;
\item[psb\_upd\_perm\_] Update strategy based on additional
  permutation data (see tools routine description).
\end{description}


\subsection{Dense Vector Data Structure}
\label{sec:vecttype}
The \hypertarget{vdata}{{\tt psb\_T\_vect\_type}} data structure
encapsulates the dense vectors in a way similar to sparse matrices,
i.e. including a base type \hypertarget{vbasedata}{{\tt
    psb\_T\_base\_vect\_type}}.  
The user will not, in general, access the vector components directly,
but rather via the routines of sec.~\ref{sec:toolsrout}. Among other
simple things, we define here an extraction method that can be used to
get a full copy of the part of the vector stored on the local
process. 

 The type declaration is shown in
figure~\ref{fig:vectype} where \fortinline|T| is a placeholder for the
data type and precision variants 
\begin{description}
\item[I] Integer;
\item[S] Single precision real;
\item[D] Double precision real;
\item[C] Single precision complex;
\item[Z] Double precision complex.
\end{description}
The actual data is contained in the polymorphic component \fortinline|v%v|; 
the separation between the application and the actual data is
essential for cases where it is necessary to link to data storage made
available elsewhere outside the direct control of the
compiler/application, e.g. data stored in a graphics  accelerator's
private memory. 
\begin{listing}[h!]
  % \begin{Sbox}
 
\ifpdf
\begin{minted}[breaklines=true,bgcolor=bg,fontsize=\small]{fortran}
  type psb_T_base_vect_type
    TYPE(KIND_), allocatable :: v(:)
  end type psb_T_base_vect_type

  type psb_T_vect_type
    class(psb_T_base_vect_type), allocatable :: v 
  end type  psb_T_vect_type
\end{minted}
\else
\begin{center}
    \begin{minipage}[tl]{0.85\textwidth}
\begin{verbatim}
  type psb_T_base_vect_type
    TYPE(KIND_), allocatable :: v(:)
  end type psb_T_base_vect_type

  type psb_T_vect_type
    class(psb_T_base_vect_type), allocatable :: v 
  end type  psb_T_vect_type

\end{verbatim}
    \end{minipage}
  \end{center}
\fi
% \end{Sbox}
%   \setlength{\fboxsep}{8pt}
%   \begin{center}
%     \fbox{\TheSbox}
%   \end{center}
  \caption{\label{fig:vectype} 
    The PSBLAS defined data type that
    contains a dense vector.} 
\end{listing}

\subsubsection{Vector Methods}
\subsubsection{get\_nrows --- Get number of  rows in a dense vector}
%\addcontentsline{toc}{paragraph}{get\_nrows}

\fortinline|nr = v%get_nrows()|

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[v] the dense vector\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The number of  rows  of dense vector \fortinline|v|.
\end{description}


\subsubsection{sizeof  --- Get memory occupation in bytes
of  a dense vector}
%\addcontentsline{toc}{paragraph}{sizeof }

\fortinline|memory_size = v%sizeof()|

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[v] the dense vector\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] The memory occupation in bytes.
\end{description}


\subsubsection{set  --- Set contents of the vector}
%\addcontentsline{toc}{paragraph}{set }

\ifpdf
\begin{minted}{fortran}
 call  v%set(alpha[,first,last])
 call  v%set(vect[,first,last])
 call  v%zero()
\end{minted}
\else
\begin{verbatim}
 call  v%set(alpha[,first,last])
 call  v%set(vect[,first,last])
 call  v%zero()
\end{verbatim}
\fi

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[v] the dense vector\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\item[alpha] A scalar value. \\ Scope: {\bf local} \\ Type: {\bf
required} \\ Intent: {\bf in}.\\ Specified as: a number of the data
type indicated in Table~\ref{tab:f90axpby}.

\item[first,last] Boundaries for setting in the vector.\\ Scope: {\bf
    local} \\ Type: {\bf optional} \\ Intent: {\bf in}.\\ Specified
  as: integers.
\item[vect] An  array \\ Scope: {\bf local} \\ Type: {\bf
required} \\ Intent: {\bf in}.\\ Specified as: a number of the data
type indicated in Table~\ref{tab:f90axpby}.
\end{description}
Note that a call to \fortinline|v%zero()| is provided as a shorthand, but
is equivalent to a call to \fortinline|v%set(zero)| with  the \fortinline|zero|
constant having the appropriate type and kind.

\begin{description}
\item[\bf On Return]
\item[v] the dense vector, with updated entries\\
Scope: {\bf local}\\
\end{description}

\subsubsection{get\_vect  --- Get a copy of the vector contents}
%\addcontentsline{toc}{paragraph}{get\_vect }

\begin{verbatim}
extv = v%get_vect([n])
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[v] the dense vector\\
Scope: {\bf local}\\
% Type: {\bf required}\\
% Intent: {\bf in}.\\
% Specified as: a object of type \spdata.
\item[n] Size to be returned\\
Scope: {\bf local}.\\
Type: {\bf optional}; default: entire vector.\\

\end{description}

\begin{description}
\item[\bf On Return]
\item[Function value] An allocatable array holding a copy of the dense
  vector contents. If the argument $n$ is specified, the size of the
  returned array equals the minimum between $n$ and the internal size
  of the vector, or 0 if $n$ is negative; otherwise, the size of the
  array is the same as the internal size of the vector.
\end{description}

\subsubsection{clone --- Clone current object}
%\addcontentsline{toc}{paragraph}{clone}
\begin{verbatim}
call  x%clone(y,info)
\end{verbatim}

\begin{description}
\item[Type:] Asynchronous.
\item[\bf On Entry]
\item[x] the dense vector.\\
Scope: {\bf local}.\\
% Type: {\bf required}.\\
% Intent: {\bf in}.\\
% Specified as: a object of type \descdata.
\end{description}

\begin{description}
\item[\bf On Return]
\item[y] A copy of the input object.
\item[info] Return code. 
\end{description}


\subsection{Preconditioner data structure}
\label{sec:prec}
Our base library  offers support for  simple well known preconditioners
like Diagonal Scaling or Block Jacobi with incomplete
factorization ILU(0). 

 A preconditioner is held in the \hypertarget{precdata}{{\tt
    psb\_Tprec\_type}} data structure reported in 
figure~\ref{fig:prectype}. The \fortinline|psb_Tprec_type| 
data type may contain a simple preconditioning matrix with the
associated communication descriptor.
%% which may be different from  the
%% system communication descriptor in the case of parallel
%% preconditioners like the Additive Schwarz one. Then the
%% \fortinline|psb_Tprec_type| may contain more than one preconditioning matrix
%% like in the case of Two-Level (in general Multi-Level) preconditioners.
%% The user can choose the type of preconditioner to be used by means of
%% the \fortinline|psb_precset| subroutine; once the type of preconditioning
%% method is specified, along with all the parameters that characterize
%% it, the preconditioner data structure can be built using the
%% \fortinline|psb_precbld| subroutine.
%% This data structure wants to be flexible enough to easily allow the
%% implementation of new kind of preconditioners.
The internal preconditioner is allocated appropriately with the
dynamic type corresponding to the desired preconditioner. 
\begin{listing}[h!]
\ifpdf
\begin{minted}[breaklines=true,bgcolor=bg,fontsize=\small]{fortran}
  type psb_Tprec_type
    class(psb_T_base_prec_type), allocatable :: prec
  end type psb_Tprec_type
\end{minted}
\else
  \small
  % \begin{Sbox}
\begin{center}
    \begin{minipage}[tl]{0.9\textwidth}
\begin{verbatim}

  type psb_Tprec_type
    class(psb_T_base_prec_type), allocatable :: prec
  end type psb_Tprec_type

\end{verbatim}
    \end{minipage}
  \end{center}
\fi
% \end{Sbox}
%   \setlength{\fboxsep}{8pt}
%   \begin{center}
%     \fbox{\TheSbox}
%   \end{center}
  \caption{\label{fig:prectype}The PSBLAS defined data type that contains a preconditioner.}
\end{listing}

%% \subsection{Named Constants}
%% \label{sec:prec_constants}
%% \begin{description}
%% \item[f\_ilu\_n\_] Incomplete LU factorization with $n$ levels of
%%   fill-in; currently only $n=0$ is implemented;
%% \item[f\_slu\_]  Sparse factorization using SuperLU;
%% \item[f\_umf\_]  Sparse factorization using UMFPACK;
%% \item[add\_ml\_prec\_] Additive multilevel correction;
%% \item[mult\_ml\_prec\_] Multiplicative multilevel correction;
%% \item[pre\_smooth\_] Pre-smoothing in applying multiplicative
%%   multilevel corrections;
%% \item[post\_smooth\_] Post-smoothing in applying multiplicative
%%   multilevel corrections;
%% \item[smooth\_both\_] Two-sided (i.e. symmetric) smoothing in applying multiplicative
%%   multilevel corrections;
%% \item[mat\_distr\_] Coarse matrix distributed among processes
%% \item[mat\_repl\_] Coarse matrix replicated among processes
%% \end{description}


% \subsection{Data structure Methods}
% \label{sec:dataquery}
\subsection{Heap data structure}

Among the tools routines of sec.~\ref{sec:toolsrout}, we have a number
of sorting utilities; the heap sort is implemented in terms of heaps
having the following signatures:
\begin{description}
\item[\tt psb\_T\_heap]: a heap containing elements of type T, where T
  can be \fortinline|i,s,c,d,z| for integer, real and complex data;
\item[\tt psb\_T\_idx\_heap]: a heap containing elements of type T, as
  above, together with an integer index.
\end{description}
Given a heap object, the following methods are defined on it:
\begin{description}
\item[init] Initialize memory; also choose ascending or descending
  order;
\item[howmany] Current heap occupancy;
\item[insert] Add an item (or an item and its index);
\item[get\_first] Remove and return the first element;
\item[dump] Print on file;
\item[free] Release memory.
\end{description}
These objects are used to implement the factorization
and approximate inversion algorithms. 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "userguide"
%%% End: