0000926: IMPLEMENTED: AMD ordering for matrices with dense rows

Viewing Issue Advanced Details [ Jump to Notes ]

[ View Simple ] [ Issue History ] [ Print ]

Category

Severity

Reproducibility

Date Submitted

Last Update

0000926

[ALGLIB] Linear algebra

feature

have not tried

2021-07-22 17:27

2021-08-28 22:42

Reporter

SergeyB

View Status

public

Assigned To

SergeyB

Priority

normal

Resolution

implemented

Platform

Status

resolved

Projection

none

OS Version

ETA

none

Fixed in Version

3.18.0

Product Version

Target Version

3.18.0

Product Build

Summary

0000926: IMPLEMENTED: AMD ordering for matrices with dense rows

Description

Implemented new AMD ordering algorithm for matrices with dense/nearly dense rows, set as default one for sparse Cholesky/LDLT.

Details: original AMD ordering algorithm has O(N^2) running time for a matrix with just one dense row. Improved algorithm postpones ordering of rows with too many nonzero elements (including ones which are not dense, but still has more nonzeros than typical row) and handles them later, at the second ordering round.

Steps To Reproduce

Additional Information

Programming language

Unspecified

Attached Files

Relationships

There are no notes attached to this issue.

Issue History
Date Modified	Username	Field	Change
2021-07-22 17:27	SergeyB	New Issue
2021-07-22 17:27	SergeyB	Status	new => assigned
2021-07-22 17:27	SergeyB	Assigned To	=> SergeyB
2021-07-22 17:27	SergeyB	Programming language	=> Unspecified
2021-08-28 22:42	SergeyB	Summary	approximate minimum degree algorithm for matrices with dense rows => IMPLEMENTED: AMD ordering for matrices with dense rows
2021-08-28 22:42	SergeyB	Description Updated
2021-08-28 22:42	SergeyB	Status	assigned => resolved
2021-08-28 22:42	SergeyB	Fixed in Version	=> 3.18.0
2021-08-28 22:42	SergeyB	Resolution	open => implemented

Mantis 1.1.6[^]