dsm_module – NumDiff

Jacobian partitioning using the DSM algorithm.

Reference

Argonne National Laboratory. MINPACK Project. July 1983. Thomas F. Coleman, Burton S. Garbow, Jorge J. More
Thomas F. Coleman, Burton S. Garbow, Jorge J. More, "Algorithm 618: FORTRAN subroutines for estimating sparse Jacobian Matrices", ACM Transactions on Mathematical Software (TOMS), Volume 10 Issue 3, Sept. 1984, Pages 346-347

History

Jacob Williams, Nov. 2016, extensive refactoring into modern Fortran.

Uses

- numdiff_kinds_module
Help

Graph Key

Nodes of different colours represent the following:

Solid arrows point from a submodule to the (sub)module which it is descended from. Dashed arrows point from a module or program unit to modules which it uses.

Used by

Help

Graph Key

Nodes of different colours represent the following:

Solid arrows point from a submodule to the (sub)module which it is descended from. Dashed arrows point from a module or program unit to modules which it uses.

Subroutines

public subroutine dsm(m, n, npairs, indrow, indcol, ngrp, maxgrp, mingrp, info, ipntr, jpntr)

The purpose of dsm is to determine an optimal or near- optimal consistent partition of the columns of a sparse m by n matrix a.

Arguments

Type	Intent	Attributes		Name
integer,	intent(in)		::	m	number of rows of `a` (>0)
integer,	intent(in)		::	n	number of columns of `a` (>0)
integer,	intent(in)		::	npairs	number of (`indrow`,`indcol`) pairs used to describe the sparsity pattern of `a` (>0)
integer,	intent(inout),	dimension(npairs)	::	indrow	an integer array of length `npairs`. on input `indrow` must contain the row indices of the non-zero elements of `a`. on output `indrow` is permuted so that the corresponding column indices are in non-decreasing order. the column indices can be recovered from the array `jpntr`.
integer,	intent(inout),	dimension(npairs)	::	indcol	an integer array of length `npairs`. on input `indcol` must contain the column indices of the non-zero elements of `a`. on output `indcol` is permuted so that the corresponding row indices are in non-decreasing order. the row indices can be recovered from the array `ipntr`.
integer,	intent(out),	dimension(n)	::	ngrp	specifies the partition of the columns of `a`. column `jcol` belongs to group `ngrp(jcol)`.
integer,	intent(out)		::	maxgrp	the number of groups in the partition of the columns of `a`.
integer,	intent(out)		::	mingrp	a lower bound for the number of groups in any consistent partition of the columns of `a`.
integer,	intent(out)		::	info	for normal termination `info = 1`. if `m`, `n`, or `npairs` is not positive, then `info = 0`. if the k-th element of `indrow` is not an integer between 1 and m or the k-th element of `indcol` is not an integer between 1 and n, then `info = -k`.
integer,	intent(out),	dimension(m+1)	::	ipntr	an integer output array of length `m + 1` which specifies the locations of the column indices in `indcol`. the column indices for row `i` are `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`. note that `ipntr(m+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	intent(out),	dimension(n+1)	::	jpntr	jpntr is an integer output array of length n + 1 which specifies the locations of the row indices in indrow. the row indices for column j are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(n+1)-1` is then the number of non-zero elements of the matrix `a`.

private subroutine degr(n, indrow, jpntr, indcol, ipntr, ndeg, iwa)

Given the sparsity pattern of an m by n matrix a, this subroutine determines the degree sequence for the intersection graph of the columns of a.

Arguments

Type	Intent	Attributes		Name
integer,	intent(in)		::	n	a positive integer input variable set to the number of columns of `a`.
integer,	intent(in),	dimension(*)	::	indrow	an integer input array which contains the row indices for the non-zeroes in the matrix `a`.
integer,	intent(in),	dimension(n+1)	::	jpntr	an integer input array of length `n + 1` which specifies the locations of the row indices in `indrow`. the row indices for column `j` are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(n+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	intent(in),	dimension(*)	::	indcol	an integer input array which contains the column indices for the non-zeroes in the matrix `a`.
integer,	intent(in),	dimension(*)	::	ipntr	an integer input array of length `m + 1` which specifies the locations of the column indices in `indcol`. the column indices for row `i` are `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`. note that `ipntr(m+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	intent(out),	dimension(n)	::	ndeg	an integer output array of length `n` which specifies the degree sequence. the degree of the `j`-th column of `a` is `ndeg(j)`.
integer,		dimension(n)	::	iwa	an integer work array of length `n`

private subroutine ido(m, n, Indrow, Jpntr, Indcol, Ipntr, Ndeg, List, Maxclq, Iwa1, Iwa2, Iwa3, Iwa4)

given the sparsity pattern of an m by n matrix a, this subroutine determines an incidence-degree ordering of the columns of a.

Arguments

Type	Intent	Attributes		Name
integer,	intent(in)		::	m	a positive integer input variable set to the number of rows of `a`.
integer,	intent(in)		::	n	a positive integer input variable set to the number of columns of `a`.
integer,	intent(in),	dimension(*)	::	Indrow	an integer input array which contains the row indices for the non-zeroes in the matrix `a`.
integer,	intent(in),	dimension(n+1)	::	Jpntr	an integer input array of length `n + 1` which specifies the locations of the row indices in `indrow`. the row indices for column `j` are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(n+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	intent(in),	dimension(*)	::	Indcol	an integer input array which contains the column indices for the non-zeroes in the matrix `a`.
integer,	intent(in),	dimension(m+1)	::	Ipntr	an integer input array of length `m + 1` which specifies the locations of the column indices in `indcol`. the column indices for row `i` are `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`. note that `ipntr(m+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	intent(in),	dimension(n)	::	Ndeg	an integer input array of length `n` which specifies the degree sequence. the degree of the `j`-th column of `a` is `ndeg(j)`.
integer,	intent(out),	dimension(n)	::	List	an integer output array of length `n` which specifies the incidence-degree ordering of the columns of `a`. the `j`-th column in this order is `list(j)`.
integer,	intent(out)		::	Maxclq	an integer output variable set to the size of the largest clique found during the ordering.
integer,		dimension(0:n-1)	::	Iwa1	integer work array of length `n`.
integer,		dimension(n)	::	Iwa2	integer work array of length `n`.
integer,		dimension(n)	::	Iwa3	integer work array of length `n`.
integer,		dimension(n)	::	Iwa4	integer work array of length `n`.

private subroutine numsrt(n, Nmax, Num, Mode, Index, Last, Next)

Given a sequence of integers, this subroutine groups together those indices with the same sequence value and, optionally, sorts the sequence into either ascending or descending order.

Arguments

Type	Intent	Attributes		Name
integer,	intent(in)		::	n	a positive integer input variable.
integer			::	Nmax	a positive integer input variable.
integer,		dimension(n)	::	Num	an input array of length `n` which contains the sequence of integers to be grouped and sorted. it is assumed that the integers are each from the set `0,1,...,nmax`.
integer			::	Mode	an integer input variable. the sequence `num` is sorted in ascending order if `mode` is positive and in descending order if `mode` is negative. if `mode` is 0, no sorting is done.
integer,		dimension(n)	::	Index	an integer output array of length `n` set so that the sequence `num(index(i)), i = 1,2,...,n` is sorted according to the setting of mode. if `mode` is 0, `index` is not referenced.
integer,		dimension(0:Nmax)	::	Last	an integer output array of length `nmax + 1`. the index of `num` for the last occurrence of `l` is `last(l)` for any `l = 0,1,...,nmax` unless `last(l) = 0`. in this case `l` does not appear in `num`.
integer,		dimension(n)	::	Next	an integer output array of length `n`. if `num(k) = l`, then the index of `num` for the previous occurrence of `l` is `next(k)` for any `l = 0,1,...,nmax` unless `next(k) = 0`. in this case there is no previous occurrence of `l` in `num`.

private subroutine seq(n, Indrow, Jpntr, Indcol, Ipntr, List, Ngrp, Maxgrp, Iwa)

given the sparsity pattern of an m by n matrix a, this subroutine determines a consistent partition of the columns of a by a sequential algorithm.

Arguments

Type	Attributes		Name
integer		::	n	a positive integer input variable set to the number of columns of `a`.
integer,	dimension(*)	::	Indrow	an integer input array which contains the row indices for the non-zeroes in the matrix `a`.
integer,	dimension(n+1)	::	Jpntr	an integer input array of length `n + 1` which specifies the locations of the row indices in `indrow`. the row indices for column `j` are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(n+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	dimension(*)	::	Indcol	an integer input array which contains the column indices for the non-zeroes in the matrix `a`.
integer,	dimension(*)	::	Ipntr	an integer input array of length `m + 1` which specifies the locations of the column indices in `indcol`. the column indices for row `i` are `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`. note that `ipntr(m+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	dimension(n)	::	List	an integer input array of length `n` which specifies the order to be used by the sequential algorithm. the `j`-th column in this order is `list(j)`.
integer,	dimension(n)	::	Ngrp	an integer output array of length `n` which specifies the partition of the columns of `a`. column `jcol` belongs to group `ngrp(jcol)`.
integer		::	Maxgrp	an integer output variable which specifies the number of groups in the partition of the columns of `a`.
integer,	dimension(n)	::	Iwa	an integer work array of length `n`

private subroutine setr(m, n, Indrow, Jpntr, Indcol, Ipntr, Iwa)

given a column-oriented definition of the sparsity pattern of an m by n matrix a, this subroutine determines a row-oriented definition of the sparsity pattern of a.

Arguments

Type	Intent	Attributes		Name
integer,	intent(in)		::	m	a positive integer input variable set to the number of rows of `a`.
integer,	intent(in)		::	n	a positive integer input variable set to the number of columns of `a`.
integer,		dimension(*)	::	Indrow	an integer input array which contains the row indices for the non-zeroes in the matrix `a`.
integer,		dimension(n+1)	::	Jpntr	an integer input array of length `n + 1` which specifies the locations of the row indices in `indrow`. the row indices for column `j` are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(n+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,		dimension(*)	::	Indcol	an integer output array which contains the column indices for the non-zeroes in the matrix `a`.
integer,		dimension(m+1)	::	Ipntr	an integer output array of length `m + 1` which specifies the locations of the column indices in `indcol`. the column indices for row `i` are `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`. note that `ipntr(1)` is set to 1 and that `ipntr(m+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,		dimension(m)	::	Iwa	an integer work array of length `m`.

private subroutine slo(n, Indrow, Jpntr, Indcol, Ipntr, Ndeg, List, Maxclq, Iwa1, Iwa2, Iwa3, Iwa4)

given the sparsity pattern of an m by n matrix a, this subroutine determines the smallest-last ordering of the columns of a.

Arguments

Type	Attributes		Name
integer		::	n	a positive integer input variable set to the number of columns of `a`.
integer,	dimension(*)	::	Indrow	an integer input array which contains the row indices for the non-zeroes in the matrix `a`.
integer,	dimension(n+1)	::	Jpntr	an integer input array of length `n + 1` which specifies the locations of the row indices in `indrow`. the row indices for column `j` are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(n+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	dimension(*)	::	Indcol	an integer input array which contains the column indices for the non-zeroes in the matrix `a`.
integer,	dimension(*)	::	Ipntr	an integer input array of length `m + 1` which specifies the locations of the column indices in `indcol`. the column indices for row `i` are `indcol(k), k = ipntr(i),...,ipntr(i+1)-1`. note that `ipntr(m+1)-1` is then the number of non-zero elements of the matrix `a`.
integer,	dimension(n)	::	Ndeg	an integer input array of length `n` which specifies the degree sequence. the degree of the `j`-th column of `a` is `ndeg(j)`.
integer,	dimension(n)	::	List	an integer output array of length `n` which specifies the smallest-last ordering of the columns of `a`. the `j`-th column in this order is `list(j)`.
integer		::	Maxclq	an integer output variable set to the size of the largest clique found during the ordering.
integer,	dimension(0:n-1)	::	Iwa1	integer work array of length `n`
integer,	dimension(n)	::	Iwa2	integer work array of length `n`
integer,	dimension(n)	::	Iwa3	integer work array of length `n`
integer,	dimension(n)	::	Iwa4	integer work array of length `n`

private subroutine srtdat(n, Nnz, Indrow, Indcol, Jpntr, Iwa)

given the non-zero elements of an m by n matrix a in arbitrary order as specified by their row and column indices, this subroutine permutes these elements so that their column indices are in non-decreasing order.

Arguments

Type	Attributes		Name
integer		::	n	a positive integer input variable set to the number of columns of `a`.
integer		::	Nnz	a positive integer input variable set to the number of non-zero elements of `a`.
integer,	dimension(Nnz)	::	Indrow	an integer array of length `nnz`. on input `indrow` must contain the row indices of the non-zero elements of `a`. on output `indrow` is permuted so that the corresponding column indices of `indcol` are in non-decreasing order.
integer,	dimension(Nnz)	::	Indcol	an integer array of length `nnz`. on input `indcol` must contain the column indices of the non-zero elements of `a`. on output `indcol` is permuted so that these indices are in non-decreasing order.
integer,	dimension(n+1)	::	Jpntr	an integer output array of length `n + 1` which specifies the locations of the row indices in the output `indrow`. the row indices for column `j` are `indrow(k), k = jpntr(j),...,jpntr(j+1)-1`. note that `jpntr(1)` is set to 1 and that `jpntr(n+1)-1` is then `nnz`.
integer,	dimension(n)	::	Iwa	an integer work array of length `n`.

public subroutine fdjs(m, n, Col, Ind, Npntr, Ngrp, Numgrp, d, Fjacd, Fjac)

Given a consistent partition of the columns of an m by n jacobian matrix into groups, this subroutine computes approximations to those columns in a given group. the approximations are stored into either a column-oriented or a row-oriented pattern.

Arguments

Type	Intent	Attributes		Name
integer,	intent(in)		::	m	a positive integer input variable set to the number of rows of the jacobian matrix.
integer,	intent(in)		::	n	a positive integer input variable set to the number of columns of the jacobian matrix.
logical,	intent(in)		::	Col	a logical input variable. if `col` is set true, then the jacobian approximations are stored into a column-oriented pattern. if `col` is set false, then the jacobian approximations are stored into a row-oriented pattern.
integer,		dimension(*)	::	Ind	an integer input array which contains the row indices for the non-zeroes in the jacobian matrix if `col` is true, and contains the column indices for the non-zeroes in the jacobian matrix if `col` is false.
integer,		dimension(*)	::	Npntr	an integer input array which specifies the locations of the row indices in `ind` if `col` is true, and specifies the locations of the column indices in `ind` if `col` is false. if `col` is true, the indices for column `j` are `ind(k), k = npntr(j),...,npntr(j+1)-1`. if `col` is false, the indices for row `i` are `ind(k), k = npntr(i),...,npntr(i+1)-1`. *Note* that `npntr(n+1)-1` if `col` is true, or `npntr(m+1)-1` if `col` is false, is then the number of non-zero elements of the jacobian matrix.
integer,		dimension(n)	::	Ngrp	an integer input array of length `n` which specifies the partition of the columns of the jacobian matrix. column `jcol` belongs to group `ngrp(jcol)`.
integer			::	Numgrp	a positive integer input variable set to a group number in the partition. the columns of the jacobian matrix in this group are to be estimated on this call.
real(kind=wp),		dimension(n)	::	d	an input array of length `n` which contains the difference parameter vector for the estimate of the jacobian matrix columns in group `numgrp`.
real(kind=wp),		dimension(m)	::	Fjacd	an input array of length `m` which contains an approximation to the difference vector `jac*d`, where `jac` denotes the jacobian matrix.
real(kind=wp),		dimension(*)	::	Fjac	an output array of length `nnz`, where `nnz` is the number of its non-zero elements. at each call of `fdjs`, `fjac` is updated to include the non-zero elements of the jacobian matrix for those columns in group `numgrp`. `fjac` should not be altered between successive calls to `fdjs`.

dsm_module Module

Contents

Subroutines

Reference

History

Uses

Used by

Subroutines

public subroutine dsm(m, n, npairs, indrow, indcol, ngrp, maxgrp, mingrp, info, ipntr, jpntr)

Arguments

private subroutine degr(n, indrow, jpntr, indcol, ipntr, ndeg, iwa)

Arguments

private subroutine ido(m, n, Indrow, Jpntr, Indcol, Ipntr, Ndeg, List, Maxclq, Iwa1, Iwa2, Iwa3, Iwa4)

Arguments

private subroutine numsrt(n, Nmax, Num, Mode, Index, Last, Next)

Arguments

private subroutine seq(n, Indrow, Jpntr, Indcol, Ipntr, List, Ngrp, Maxgrp, Iwa)

Arguments

private subroutine setr(m, n, Indrow, Jpntr, Indcol, Ipntr, Iwa)

Arguments

private subroutine slo(n, Indrow, Jpntr, Indcol, Ipntr, Ndeg, List, Maxclq, Iwa1, Iwa2, Iwa3, Iwa4)

Arguments

private subroutine srtdat(n, Nnz, Indrow, Indcol, Jpntr, Iwa)

Arguments

public subroutine fdjs(m, n, Col, Ind, Npntr, Ngrp, Numgrp, d, Fjacd, Fjac)

Arguments