Tellegen's Principle into Practice

A. Bostan; G. Lecerf; É Schost

doi:10.1145/860854.860870

Tellegen's Principle into Practice

A. Bostan
, G. Lecerf
, É Schost

Research output: Contribution to conference › Paper › peer-review

94 Citations (Scopus)

Abstract

The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.

Original language	English
Pages	37-44
Number of pages	8
DOIs	https://doi.org/10.1145/860854.860870
Publication status	Published - 1 Jan 2003
Event	Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) - Philadelphia, PA., United States Duration: 3 Aug 2003 → 6 Aug 2003

Conference

Conference	Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003)
Country/Territory	United States
City	Philadelphia, PA.
Period	3/08/03 → 6/08/03

Keywords

Computer algebra
Interpolation
Polynomial evaluation
Tellegen's principle
Transposition principle

Access to Document

10.1145/860854.860870

Cite this

@conference{2a77a8277aa64bbda38a69c9e2d8460d,

title = "Tellegen's Principle into Practice",

abstract = "The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.",

keywords = "Computer algebra, Interpolation, Polynomial evaluation, Tellegen's principle, Transposition principle",

author = "A. Bostan and G. Lecerf and {\'E} Schost",

year = "2003",

month = jan,

day = "1",

doi = "10.1145/860854.860870",

language = "English",

pages = "37--44",

note = "Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) ; Conference date: 03-08-2003 Through 06-08-2003",

}

TY - CONF

T1 - Tellegen's Principle into Practice

AU - Bostan, A.

AU - Lecerf, G.

AU - Schost, É

PY - 2003/1/1

Y1 - 2003/1/1

N2 - The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.

AB - The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.

KW - Computer algebra

KW - Interpolation

KW - Polynomial evaluation

KW - Tellegen's principle

KW - Transposition principle

U2 - 10.1145/860854.860870

DO - 10.1145/860854.860870

M3 - Paper

AN - SCOPUS:1542270107

SP - 37

EP - 44

T2 - Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003)

Y2 - 3 August 2003 through 6 August 2003

ER -

Tellegen's Principle into Practice

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this