#include <deal.II/lac/matrix_scaling.h>

Detailed Description

This class provides access to various matrix scaling algorithms. The scaling algorithms scale the matrix in place by the action of two diagonal matrices: one acting on the rows and one acting on the columns. The algorithms implemented here are the Sinkhorn-Knopp algorithm described in [149] and the scaling algorithm that preserves symmetry described in [148].

The parallel implementation with MPI of the algorithms follows the description in [4]. The diagonals of the scaling matrices are distributed between the MPI processes following the row distribution of the matrix. The diagonal of the column scaling is distributed in a balanced way if the scaled matrix is not square.

Instantiations

There are instantiations of this class for SparseMatrix<double>, SparseMatrix<float>, FullMatrix<double>, FullMatrix<float>, BlockSparseMatrix<float>, BlockSparseMatrix<double>, SparseMatrixEZ<double> and SparseMatrixEZ<float>.

The distributed matrices supported are TrilinosWrappers::SparseMatrix and PETScWrappers::MPI::SparseMatrix.

Definition at line 63 of file matrix_scaling.h.

Inheritance diagram for MatrixScaling:

[legend]

Classes
struct	AdditionalData

Public Types
enum class	ConvergenceNormType { l1 , l_infty }

Public Member Functions
	MatrixScaling (const AdditionalData &control=AdditionalData())

	~MatrixScaling ()=default

template<class Matrix >
bool	find_scaling_and_scale_matrix (Matrix &matrix)

template<class Matrix , class VectorType >
bool	find_scaling_and_scale_linear_system (Matrix &matrix, VectorType &rhs)

template<class VectorType >
void	scale_system_solution (VectorType &sol) const

const Vector< double > &	get_row_scaling () const

const Vector< double > &	get_column_scaling () const

template<class Archive >
void	serialize (Archive &ar, const unsigned int version)

Querying the observer pointers an object has.
unsigned int	n_subscriptions () const

template<typename StreamType >
void	list_subscribers (StreamType &stream) const

void	list_subscribers () const

Static Public Member Functions
static ::ExceptionBase &	ExcInUse (int arg1, std::string arg2, std::string arg3)

static ::ExceptionBase &	ExcNoSubscriber (std::string arg1, std::string arg2)

Private Member Functions
template<class Matrix >
bool	do_l1_scaling (Matrix &matrix, const unsigned int nsteps)

template<class Matrix >
bool	do_linfty_scaling (Matrix &matrix, const unsigned int nsteps)

template<class Matrix >
bool	do_sk_scaling (Matrix &matrix, const unsigned int nsteps)

template<typename Number >
bool	check_convergence (const Vector< Number > &row_col_norm, const ConvergenceNormType &norm_type) const

template<typename Number >
bool	check_convergence (const Vector< Number > &row_norm, const Vector< Number > &col_norm, const ConvergenceNormType &norm_type) const

bool	check_convergence (const Vector< double > &local_row_col_norm, const ConvergenceNormType &norm_type, const MPI_Comm mpi_communicator) const

bool	check_convergence (const Vector< double > &local_row_norm, const Vector< double > &local_col_norm, const ConvergenceNormType &norm_type, const MPI_Comm mpi_communicator) const

void	send_prepare_col_norms (const std::map< types::global_dof_index, double > &partial_column_norms, std::map< unsigned int, std::vector< std::pair< types::global_dof_index, double > > > &send_data, Vector< double > &local_col_norms)

void	send_prepare_updated_col_norms (const std::map< unsigned int, std::vector< std::pair< types::global_dof_index, double > > > &received_data, const Vector< double > &local_col_norms, std::map< unsigned int, std::vector< std::pair< types::global_dof_index, double > > > &send_column_norms)

EnableObserverPointer functionality
Classes derived from EnableObserverPointer provide a facility to subscribe to this object. This is mostly used by the ObserverPointer class.
void	subscribe (std::atomic< bool > *const validity, const std::string &identifier="") const

void	unsubscribe (std::atomic< bool > *const validity, const std::string &identifier="") const

void	check_no_subscribers () const noexcept

Private Attributes
AdditionalData	control

Vector< double >	row_scaling

Vector< double >	column_scaling

IndexSet	locally_owned_rows

IndexSet	locally_owned_cols

IndexSet	ghost_columns

std::vector< unsigned int >	ghost_column_owners

Utilities::MPI::Partitioner	partitioner

std::atomic< unsigned int >	counter

std::map< std::string, unsigned int >	counter_map

std::vector< std::atomic< bool > * >	validity_pointers

const std::type_info *	object_info

Static Private Attributes
static std::mutex	mutex

Member Enumeration Documentation

◆ ConvergenceNormType

enum class MatrixScaling::ConvergenceNormType

strong

Vectorial norms used to check convergence in the scaling algorithms.

Enumerator
l1	l_1 vector norm
l_infty	l_infinity vector norm

Definition at line 69 of file matrix_scaling.h.

Constructor & Destructor Documentation

◆ MatrixScaling()

MatrixScaling::MatrixScaling ( const AdditionalData & control = AdditionalData() )

explicit

Constructor. The constructor takes a AdditionalData object that contains the parameters for the scaling algorithms and the algorithm selected.

Definition at line 91 of file matrix_scaling.cc.

◆ ~MatrixScaling()

MatrixScaling::~MatrixScaling ( )

default

Destructor.

Member Function Documentation

◆ find_scaling_and_scale_matrix()

template<class Matrix >

bool MatrixScaling::find_scaling_and_scale_matrix ( Matrix & matrix )

Scale the input matrix in place according to the selected algorithm in AdditionalData.

The function returns whether the scaling algorithm has converged or not. Convergence is not necessary to have a good scaling but it can be helpful to know if it was achieved.

Definition at line 101 of file matrix_scaling.cc.

◆ find_scaling_and_scale_linear_system()

template<class Matrix , class VectorType >

bool MatrixScaling::find_scaling_and_scale_linear_system	(	Matrix &	matrix,
		VectorType &	rhs
	)

Scale the system matrix in place according to the selected algorithm in AdditionalData and scale in place the right hand side vector rhs according to the row scaling. The solution of the scaled system can be scaled back to the original system by calling scale_system_solution().

The function returns whether the scaling algorithm has converged or not. Convergence is not necessary to have a good scaling but it can be helpful to know if it was achieved.

Definition at line 247 of file matrix_scaling.cc.

◆ scale_system_solution()

template<class VectorType >

void MatrixScaling::scale_system_solution ( VectorType & sol ) const

Scale back the linear system solution vector according to the column scaling. This function should be called after solving the scaled system obtained by calling find_scaling_and_scale_linear_system().

Definition at line 298 of file matrix_scaling.cc.

◆ get_row_scaling()

const Vector< double > & MatrixScaling::get_row_scaling ( ) const

Return a const reference to the (locally owned in distributed setting) row scaling (i.e. the diagonal of the row scaling matrix).

Definition at line 341 of file matrix_scaling.cc.

◆ get_column_scaling()

const Vector< double > & MatrixScaling::get_column_scaling ( ) const

Return a const reference to the (locally owned in distributed setting) column scaling (i.e. the diagonal of the column scaling matrix).

Definition at line 349 of file matrix_scaling.cc.

◆ do_l1_scaling()

template<class Matrix >

bool MatrixScaling::do_l1_scaling	(	Matrix &	matrix,
		const unsigned int	nsteps
	)

private

Implementation of the l1 scaling iterations in the symmetry preserving algorithm. The function returns whether the scaling algorithm has converged or not.

Definition at line 595 of file matrix_scaling.cc.

◆ do_linfty_scaling()

template<class Matrix >

bool MatrixScaling::do_linfty_scaling	(	Matrix &	matrix,
		const unsigned int	nsteps
	)

private

Implementation of the linfty scaling iterations in the symmetry preserving algorithm. The function returns whether the scaling algorithm has converged or not.

Definition at line 778 of file matrix_scaling.cc.

◆ do_sk_scaling()

template<class Matrix >

bool MatrixScaling::do_sk_scaling	(	Matrix &	matrix,
		const unsigned int	nsteps
	)

private

Implementation of the Sinkhorn-Knopp scaling iterations. The function returns whether the scaling algorithm has converged or not.

Definition at line 968 of file matrix_scaling.cc.

◆ check_convergence() [1/4]

template<typename Number >

bool MatrixScaling::check_convergence	(	const Vector< Number > &	row_col_norm,
		const ConvergenceNormType &	norm_type
	)		const

private

Definition at line 358 of file matrix_scaling.cc.

◆ check_convergence() [2/4]

template<typename Number >

bool MatrixScaling::check_convergence	(	const Vector< Number > &	row_norm,
		const Vector< Number > &	col_norm,
		const ConvergenceNormType &	norm_type
	)		const

private

Definition at line 394 of file matrix_scaling.cc.

◆ check_convergence() [3/4]

bool MatrixScaling::check_convergence	(	const Vector< double > &	local_row_col_norm,
		const ConvergenceNormType &	norm_type,
		const MPI_Comm	mpi_communicator
	)		const

private

Definition at line 438 of file matrix_scaling.cc.

◆ check_convergence() [4/4]

bool MatrixScaling::check_convergence	(	const Vector< double > &	local_row_norm,
		const Vector< double > &	local_col_norm,
		const ConvergenceNormType &	norm_type,
		const MPI_Comm	mpi_communicator
	)		const

private

Definition at line 482 of file matrix_scaling.cc.

◆ send_prepare_col_norms()

void MatrixScaling::send_prepare_col_norms	(	const std::map< types::global_dof_index, double > &	partial_column_norms,
		std::map< unsigned int, std::vector< std::pair< types::global_dof_index, double > > > &	send_data,
		Vector< double > &	local_col_norms
	)

private

Definition at line 538 of file matrix_scaling.cc.

◆ send_prepare_updated_col_norms()

void MatrixScaling::send_prepare_updated_col_norms	(	const std::map< unsigned int, std::vector< std::pair< types::global_dof_index, double > > > &	received_data,
		const Vector< double > &	local_col_norms,
		std::map< unsigned int, std::vector< std::pair< types::global_dof_index, double > > > &	send_column_norms
	)

private

Definition at line 564 of file matrix_scaling.cc.

◆ n_subscriptions()

unsigned int EnableObserverPointer::n_subscriptions ( ) const

inlineinherited

Return the present number of subscriptions to this object. This allows to use this class for reference counted lifetime determination where the last one to unsubscribe also deletes the object.

Definition at line 318 of file enable_observer_pointer.h.

◆ list_subscribers() [1/2]

template<typename StreamType >

void EnableObserverPointer::list_subscribers ( StreamType & stream ) const

inlineinherited

List the subscribers to the input stream.

Definition at line 335 of file enable_observer_pointer.h.

◆ list_subscribers() [2/2]

void EnableObserverPointer::list_subscribers ( ) const

inherited

List the subscribers to deallog.

Definition at line 200 of file enable_observer_pointer.cc.

◆ serialize()

template<class Archive >

void EnableObserverPointer::serialize	(	Archive &	ar,
		const unsigned int	version
	)

inlineinherited

Read or write the data of this object to or from a stream for the purpose of serialization using the BOOST serialization library.

This function does not actually serialize any of the member variables of this class. The reason is that what this class stores is only who subscribes to this object, but who does so at the time of storing the contents of this object does not necessarily have anything to do with who subscribes to the object when it is restored. Consequently, we do not want to overwrite the subscribers at the time of restoring, and then there is no reason to write the subscribers out in the first place.

Definition at line 327 of file enable_observer_pointer.h.

◆ subscribe()

void EnableObserverPointer::subscribe	(	std::atomic< bool > *const	validity,
		const std::string &	identifier = `""`
	)		const

privateinherited

Subscribes a user of the object by storing the pointer validity. The subscriber may be identified by text supplied as identifier.

Definition at line 136 of file enable_observer_pointer.cc.

◆ unsubscribe()

void EnableObserverPointer::unsubscribe	(	std::atomic< bool > *const	validity,
		const std::string &	identifier = `""`
	)		const

privateinherited

Unsubscribes a user from the object.

Note: The identifier and the validity pointer must be the same as the one supplied to subscribe().

Definition at line 154 of file enable_observer_pointer.cc.

◆ check_no_subscribers()

void EnableObserverPointer::check_no_subscribers ( ) const

privatenoexceptinherited

Check that there are no objects subscribing to this object. If this check passes then it is safe to destroy the current object. It this check fails then this function will either abort or print an error message to deallog (by using the AssertNothrow mechanism), but will not throw an exception.

Note: Since this function is just a consistency check it does nothing in release mode.; If this function is called when there is an uncaught exception then, rather than aborting, this function prints an error message to the standard error stream and returns.

Definition at line 58 of file enable_observer_pointer.cc.

Member Data Documentation

◆ control

AdditionalData MatrixScaling::control

private

Struct that contains the parameters for the scaling algorithms.

Definition at line 280 of file matrix_scaling.h.

◆ row_scaling

Vector<double> MatrixScaling::row_scaling

private

Vector that contains the (locally owned in distributed setting) row scaling (i.e. the diagonal of the row scaling matrix).

Definition at line 286 of file matrix_scaling.h.

◆ column_scaling

Vector<double> MatrixScaling::column_scaling

private

Vector that contains the (locally owned in distributed setting) column scaling (i.e. the diagonal of the column scaling matrix).

Definition at line 292 of file matrix_scaling.h.

◆ locally_owned_rows

IndexSet MatrixScaling::locally_owned_rows

private

IndexSet storing the locally owned rows of the row scaling.

Definition at line 297 of file matrix_scaling.h.

◆ locally_owned_cols

IndexSet MatrixScaling::locally_owned_cols

private

IndexSet storing the locally owned column indexes of the column scaling.

Definition at line 302 of file matrix_scaling.h.

◆ ghost_columns

IndexSet MatrixScaling::ghost_columns

private

IndexSet storing the ghost column indexes of the column scaling. Here are stored the columns indices that will require the scaling from other MPI ranks.

Definition at line 309 of file matrix_scaling.h.

◆ ghost_column_owners

std::vector<unsigned int> MatrixScaling::ghost_column_owners

private

Vector storing the owner MPI rank of each ghost column index.

Definition at line 314 of file matrix_scaling.h.

◆ partitioner

Utilities::MPI::Partitioner MatrixScaling::partitioner

private

Partitioner for communications.

Definition at line 319 of file matrix_scaling.h.

◆ counter

std::atomic<unsigned int> EnableObserverPointer::counter

mutableprivateinherited

Store the number of objects which subscribed to this object. Initially, this number is zero, and upon destruction it shall be zero again (i.e. all objects which subscribed should have unsubscribed again).

The creator (and owner) of an object is counted in the map below if HE manages to supply identification.

We use the mutable keyword in order to allow subscription to constant objects also.

This counter may be read from and written to concurrently in multithreaded code: hence we use the std::atomic class template.

Definition at line 212 of file enable_observer_pointer.h.

◆ counter_map

std::map<std::string, unsigned int> EnableObserverPointer::counter_map

mutableprivateinherited

In this map, we count subscriptions for each different identification string supplied to subscribe().

Definition at line 218 of file enable_observer_pointer.h.

◆ validity_pointers

std::vector<std::atomic<bool> *> EnableObserverPointer::validity_pointers

mutableprivateinherited

In this vector, we store pointers to the validity bool in the ObserverPointer objects that subscribe to this class.

Definition at line 224 of file enable_observer_pointer.h.

◆ object_info

const std::type_info* EnableObserverPointer::object_info

mutableprivateinherited

Pointer to the typeinfo object of this object, from which we can later deduce the class name. Since this information on the derived class is neither available in the destructor, nor in the constructor, we obtain it in between and store it here.

Definition at line 232 of file enable_observer_pointer.h.

◆ mutex

std::mutex EnableObserverPointer::mutex

staticprivateinherited

A mutex used to ensure data consistency when accessing the mutable members of this class. This lock is used in the subscribe() and unsubscribe() functions, as well as in list_subscribers().

Definition at line 239 of file enable_observer_pointer.h.

The documentation for this class was generated from the following files:

include/deal.II/lac/matrix_scaling.h
source/lac/matrix_scaling.cc

Detailed Description

Instantiations

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Member Enumeration Documentation

◆ ConvergenceNormType

Constructor & Destructor Documentation

◆ MatrixScaling()

◆ ~MatrixScaling()

Member Function Documentation

◆ find_scaling_and_scale_matrix()

◆ find_scaling_and_scale_linear_system()

◆ scale_system_solution()

◆ get_row_scaling()

◆ get_column_scaling()

◆ do_l1_scaling()

◆ do_linfty_scaling()

◆ do_sk_scaling()

◆ check_convergence() [1/4]

◆ check_convergence() [2/4]

◆ check_convergence() [3/4]

◆ check_convergence() [4/4]

◆ send_prepare_col_norms()

◆ send_prepare_updated_col_norms()

◆ n_subscriptions()

◆ list_subscribers() [1/2]

◆ list_subscribers() [2/2]

◆ serialize()

◆ subscribe()

◆ unsubscribe()

◆ check_no_subscribers()

Member Data Documentation

◆ control

◆ row_scaling

◆ column_scaling

◆ locally_owned_rows

◆ locally_owned_cols

◆ ghost_columns

◆ ghost_column_owners

◆ partitioner

◆ counter

◆ counter_map

◆ validity_pointers

◆ object_info

◆ mutex