### Abstract

Since its inception by Gauss, the least-squares problem has frequently arisen in science, mathematics, and engineering. Iterative methods, such as Conjugate Gradient Normal Residual (CGNR), have been popular for solving sparse least-squares problems, but have historically been regarded as undesirable for dense applications due to poor convergence. We contend that this traditional 'common knowledge' should be reexamined. Preconditioned CGNR, and perhaps other iterative methods, should be considered alongside standard methods when addressing large dense least-squares problems. In this paper we present TNT, a dynamite method for solving large dense least-squares problems. TNT implements a Cholesky preconditioner for the CGNR fast iterative method. The Cholesky factorization provides a preconditioner that, in the absence of round-off error, would yield convergence in a single iteration. Through this preconditioner and good parallel scaling, TNT provides improved performance over traditional least-squares solvers allowing for accelerated investigations of scientific and engineering problems. We compare a parallel implementation of TNT to parallel implementations of other conventional methods, including the normal equations and the QR method. For the small systems tested (15000 15000 or smaller), it is shown that TNT is capable of producing smaller solution errors and executing up to 16 faster than the other tested methods. We then apply TNT to a representative rock magnetism inversion problem where it yields the best solution accuracy and execution time of all tested methods.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 987-995 |

Number of pages | 9 |

ISBN (Print) | 9781538655559 |

DOIs | |

State | Published - Aug 3 2018 |

Event | 32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018 - Vancouver, Canada Duration: May 21 2018 → May 25 2018 |

### Other

Other | 32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018 |
---|---|

Country | Canada |

City | Vancouver |

Period | 5/21/18 → 5/25/18 |

### Fingerprint

### Keywords

- Least Squares
- Preconditioned Conjugate Gradient
- Rock Magnetism

### Cite this

*Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018*(pp. 987-995). [8425520] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPSW.2018.00153

**TNT : A solver for large dense least-squares problems that takes conjugate gradient from bad in theory, to good in practice.** / Myre, Joseph M.; Frahm, Erich; Lilja, David J; Saar, Martin O.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018.*, 8425520, Institute of Electrical and Electronics Engineers Inc., pp. 987-995, 32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018, Vancouver, Canada, 5/21/18. https://doi.org/10.1109/IPDPSW.2018.00153

}

TY - GEN

T1 - TNT

T2 - A solver for large dense least-squares problems that takes conjugate gradient from bad in theory, to good in practice

AU - Myre, Joseph M.

AU - Frahm, Erich

AU - Lilja, David J

AU - Saar, Martin O.

PY - 2018/8/3

Y1 - 2018/8/3

N2 - Since its inception by Gauss, the least-squares problem has frequently arisen in science, mathematics, and engineering. Iterative methods, such as Conjugate Gradient Normal Residual (CGNR), have been popular for solving sparse least-squares problems, but have historically been regarded as undesirable for dense applications due to poor convergence. We contend that this traditional 'common knowledge' should be reexamined. Preconditioned CGNR, and perhaps other iterative methods, should be considered alongside standard methods when addressing large dense least-squares problems. In this paper we present TNT, a dynamite method for solving large dense least-squares problems. TNT implements a Cholesky preconditioner for the CGNR fast iterative method. The Cholesky factorization provides a preconditioner that, in the absence of round-off error, would yield convergence in a single iteration. Through this preconditioner and good parallel scaling, TNT provides improved performance over traditional least-squares solvers allowing for accelerated investigations of scientific and engineering problems. We compare a parallel implementation of TNT to parallel implementations of other conventional methods, including the normal equations and the QR method. For the small systems tested (15000 15000 or smaller), it is shown that TNT is capable of producing smaller solution errors and executing up to 16 faster than the other tested methods. We then apply TNT to a representative rock magnetism inversion problem where it yields the best solution accuracy and execution time of all tested methods.

AB - Since its inception by Gauss, the least-squares problem has frequently arisen in science, mathematics, and engineering. Iterative methods, such as Conjugate Gradient Normal Residual (CGNR), have been popular for solving sparse least-squares problems, but have historically been regarded as undesirable for dense applications due to poor convergence. We contend that this traditional 'common knowledge' should be reexamined. Preconditioned CGNR, and perhaps other iterative methods, should be considered alongside standard methods when addressing large dense least-squares problems. In this paper we present TNT, a dynamite method for solving large dense least-squares problems. TNT implements a Cholesky preconditioner for the CGNR fast iterative method. The Cholesky factorization provides a preconditioner that, in the absence of round-off error, would yield convergence in a single iteration. Through this preconditioner and good parallel scaling, TNT provides improved performance over traditional least-squares solvers allowing for accelerated investigations of scientific and engineering problems. We compare a parallel implementation of TNT to parallel implementations of other conventional methods, including the normal equations and the QR method. For the small systems tested (15000 15000 or smaller), it is shown that TNT is capable of producing smaller solution errors and executing up to 16 faster than the other tested methods. We then apply TNT to a representative rock magnetism inversion problem where it yields the best solution accuracy and execution time of all tested methods.

KW - Least Squares

KW - Preconditioned Conjugate Gradient

KW - Rock Magnetism

UR - http://www.scopus.com/inward/record.url?scp=85052195736&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052195736&partnerID=8YFLogxK

U2 - 10.1109/IPDPSW.2018.00153

DO - 10.1109/IPDPSW.2018.00153

M3 - Conference contribution

SN - 9781538655559

SP - 987

EP - 995

BT - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -