Employing C++ Templates in the Design of a Computer Algebra Library
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 31 | |
| Author | ||
| Contributors | ||
| License | CC Attribution 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/48029 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Production Year | 2020 | |
| Production Place | London, Canada |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
8
11
17
21
00:00
Template (C++)ComputerOperatoralgebraPolynomialTemplate (C++)Symbolic computationComputer animation
00:17
OperatoralgebraPolynomialImplementationCore dumpPrinciple of localityInterface (computing)Object (grammar)Kolmogorov complexityParallel computingCache (computing)ArchitectureCodeWeightWrapper (data mining)CodeOverhead (computing)Interface (computing)NeuroinformatikTemplate (C++)MehrprozessorsystemWrapper (data mining)Programming paradigmSemiconductor memorySymmetric algebraImplementationParallel portBuildingCore dumpBlock (periodic table)Symbolic computationCache (computing)AreaProcess (computing)Form (programming)Programming languageResultantInterface (computing)Insertion lossLibrary (computing)Computer animation
01:32
OperatoralgebraPolynomialOperations researchImplementationCore dumpPrinciple of localityModul <Datentyp>MultiplicationInterface (computing)Object (grammar)ArchitectureKolmogorov complexityCache (computing)Parallel computingWrapper (data mining)WeightCodeRootShift operatorTaylor seriesParallel portFlow separationRow (database)Interface (computing)PolynomialRootField (computer science)Sparse matrixFunctional (mathematics)Real numberComputer animation
01:55
OperatoralgebraPolynomialOperations researchCore dumpImplementationPrinciple of localityObject (grammar)Interface (computing)Cache (computing)Parallel computingArchitectureKolmogorov complexityNormal (geometry)Sparse matrixChainWrapper (data mining)CodeWeightMultiplicationModul <Datentyp>RootTaylor seriesShift operatorParallel portCharacteristic polynomialPrime idealPhysical systemHelmholtz decompositionHelmholtz decompositionTriangleChainPhysical systemOperator (mathematics)DialectBarrelled spaceImage resolutionRegular graphImplementationPolynomialComputer animation
02:11
Computer fontSocial classHierarchyAlgebraic numberPolynomialMereologyPolynomialPlanningBitTemplate (C++)Social classHierarchyCodeDynamical systemComputer animation
02:35
UsabilityOpen sourceBus (computing)Insertion lossAxiom of choiceInterface (computing)UsabilityImplementationComputer animation
02:58
UsabilityOpen sourceCodeHierarchySymmetric matrixNatural numberAlgebraic numberINTEGRALTime domainEuklidischer RaumGreatest common divisorSocial classRing (mathematics)Element (mathematics)Object (grammar)Interface (computing)SoftwareHierarchyMathematicianCodeInterface (computing)Ring (mathematics)Social classObject (grammar)GradientElement (mathematics)Sinc functionSymbolic computationObject-oriented programmingComputer animation
03:36
UsabilityOpen sourceAlgebraic numberSocial classElement (mathematics)Ring (mathematics)HierarchyObject (grammar)CodeSymmetric matrixNatural numberInterface (computing)Kolmogorov complexityCodeEncapsulation (object-oriented programming)INTEGRALTime domainEuklidischer RaumGreatest common divisorCodeInterface (computing)Complex (psychology)Student's t-testCore dumpWrapper (data mining)Encapsulation (object-oriented programming)Computer animation
03:55
UsabilityOpen sourceElement (mathematics)HierarchyAlgebraic numberSocial classRing (mathematics)Object (grammar)Natural numberCodeSymmetric matrixInterface (computing)Encapsulation (object-oriented programming)CodeKolmogorov complexityType theoryINTEGRALTime domainGreatest common divisorEuklidischer RaumMathematicsType theoryInterface (computing)Degree (graph theory)Computer programmingDifferent (Kate Ryan album)TypprüfungTypsichere SpracheMathematicsProgramming languageComputer animation
04:23
Type theoryImplementationHierarchyAlgebraic numberPolymorphism (materials science)Operations researchTime domainDomain nameEuklidischer RingMathematicsPolynomialTypprüfungSocial classAlgebraic structureRing (mathematics)Module (mathematics)CodeHierarchy1 (number)IntegerDirection (geometry)Data structureNumbering schemeComputer animation
04:59
Type theoryHierarchyImplementationAlgebraic numberOperations researchPolymorphism (materials science)Time domainSeries (mathematics)Domain nameCodeRun time (program lifecycle phase)CompilerDivisor (algebraic geometry)Run time (program lifecycle phase)Social classCodeProgramming languageModule (mathematics)IntegerRing (mathematics)Series (mathematics)PolynomialClosed setMultiplication signComputer animation
05:27
Run time (program lifecycle phase)MathematicsCategory of beingType theoryAlgebraic numberInstance (computer science)Boolean algebraRing (mathematics)Variable (mathematics)Social classInstance (computer science)Enumerated typeVariable (mathematics)InformationRing (mathematics)PolynomialMathematical singularityMachine visionComputer animation
05:58
Run time (program lifecycle phase)MathematicsCategory of beingType theoryAlgebraic numberRing (mathematics)Social classElement (mathematics)Variable (mathematics)Instance (computer science)Boolean algebraIdentical particlesElement (mathematics)CuboidRing (mathematics)Flow separationMatching (graph theory)Social classError messageMultiplication signArithmetic meanRun time (program lifecycle phase)Category of beingMathematicsEuklidischer RaumHierarchyType theoryINTEGRALComputer animation
06:33
Run time (program lifecycle phase)MathematicsCategory of beingAlgebraic numberType theorySocial classElement (mathematics)Ring (mathematics)Operations researchInstance (computer science)Boolean algebraVariable (mathematics)Identical particlesObject (grammar)Element (mathematics)Object-oriented programmingRing (mathematics)AbstractionSocial classPolymorphism (materials science)Casting (performing arts)Computer animation
07:00
MathematicsRun time (program lifecycle phase)Category of beingHierarchyAlgebraic numberType theorySocial classRing (mathematics)Element (mathematics)Variable (mathematics)Instance (computer science)Boolean algebraIdentical particlesOperations researchTypprüfungHierarchyCodeTemplate (C++)MathematicsRun time (program lifecycle phase)Multiplication signComputer animation
07:27
Computer fontTemplate (C++)Control flowComputer programCompilation albumCode generationInformation overloadCompilerImage resolutionCodePerformance appraisalParameter (computer programming)Insertion lossTemplate (C++)Term (mathematics)CodeMetaprogrammierungSocial classImage resolutionFunctional (mathematics)Multiplication signInformation overloadParameter (computer programming)Macro (computer science)Power (physics)Compilation albumPerformance appraisalComputer programmingResultantTopological algebraReal-time operating systemWeightXMLComputer animation
08:31
CompilerTemplate (C++)Performance appraisalCodeMultiplication signCodeImage resolutionFunctional (mathematics)Information overloadPerformance appraisalCategory of beingGroup actionComputer animation
08:58
CompilerTemplate (C++)CodePerformance appraisalImage resolutionInformation overloadStrutSoftware testingState diagramPoint (geometry)Type theoryParameter (computer programming)Functional (mathematics)Template (C++)Interior (topology)Macro (computer science)Distribution (mathematics)2 (number)Multiplication signNamespaceImage resolutionGroup actionShared memoryHypermediaVolumenvisualisierungInformation overloadSoftware testingTape driveComputer animation
10:22
Computer fontAlgebraic numberHierarchySocial classMathematicsTemplate (C++)AbstractionDefault (computer science)Interface (computing)Interface (computing)Inheritance (object-oriented programming)Parameter (computer programming)Ring (mathematics)Time domainINTEGRALDivisor (algebraic geometry)Template (C++)HierarchyRun time (program lifecycle phase)Series (mathematics)Declarative programmingParameter (computer programming)Interface (computing)Social classEuklidischer RingDefault (computer science)Type theoryFunctional (mathematics)Symbolic computationMathematicsPolymorphism (materials science)Message passingInterface (computing)Multiplication signXMLComputer animation
11:15
Social classFluid staticsAlgebraic numberHierarchyPolymorphism (materials science)Template (C++)Pattern languageInheritance (object-oriented programming)Function (mathematics)Image resolutionParameter (computer programming)Series (mathematics)IntegerDivisor (algebraic geometry)Error messageCompilerTime domainType theoryHypermediaRing (mathematics)Rational numberSocial classMultiplication signHierarchyInheritance (object-oriented programming)Fitness functionKey (cryptography)WeightComa BerenicesError messageSeries (mathematics)PolynomialCompilerPolygonDeclarative programmingFunctional (mathematics)Parameter (computer programming)Domain nameIntegerValidity (statistics)Euklidischer RingTemplate (C++)Interface (computing)Computer animation
12:55
Algebraic numberHierarchySocial classConstructor (object-oriented programming)Data conversionRational numberMechanism designNatural numberSequelSeries (mathematics)Einbettung <Mathematik>Data conversionRing (mathematics)PolynomialIntegerComputer animation
13:18
Social classAlgebraic numberHierarchyConstructor (object-oriented programming)Data conversionRun time (program lifecycle phase)Type theoryIntegerError messageCompilerIntegerSoftware frameworkConstructor (object-oriented programming)PolygonRing (mathematics)Rational numberData conversionPolynomialRun time (program lifecycle phase)Social classPosition operatorRevision controlCompilation albumMultiplication signMachine visionComputer animation
13:53
Computer fontSocial classPolynomialHierarchyAlgebraic numberExtension (kinesiology)AbstractionTemplate (C++)CoefficientRing (mathematics)Symbolic computationSocial classPolynomialHierarchy2 (number)CoefficientParameter (computer programming)Template (C++)Ring (mathematics)Rational numberCodeString (computer science)Device driverFormal grammarError messageXMLComputer animation
14:36
HierarchySocial classPolynomialAlgebraic numberAbstractionExtension (kinesiology)Template (C++)CoefficientString (computer science)Ring (mathematics)Type theoryString (computer science)Template (C++)HypermediaComputer animation
14:51
PolynomialSocial classAlgebraic numberHierarchyAbstractionExtension (kinesiology)Template (C++)Ring (mathematics)Type theoryTime domainINTEGRALEuklidischer RaumCoefficientString (computer science)Semiconductor memoryTopological algebraBit rateRight angleSocial classError messageCompilerType theoryIntegral domainINTEGRALPolynomialEuklidischer RaumIntegerRational numberRing (mathematics)PolynomringComputer animation
15:29
Ring (mathematics)CompilerError messageMetaprogrammierungForcePerformance appraisalTemplate (C++)Maxima and minimaInterface (computing)CoefficientParameter (computer programming)Error messageCoefficientCompilerImplementationSoftware developerPolynomialCompilation albumTemplate (C++)Ring (mathematics)Social classSymbolic computationFamilyMusical ensembleMachine visionRoundness (object)GradientRoutingFluid staticsComputer animation
16:26
Different (Kate Ryan album)CoefficientRing (mathematics)Inheritance (object-oriented programming)Template (C++)AerodynamicsInterface (computing)PolynomialInheritance (object-oriented programming)Ring (mathematics)Machine visionSocial classPerformance appraisalMultiplication signType theoryData structureComputer animation
17:04
CoefficientRing (mathematics)Different (Kate Ryan album)Inheritance (object-oriented programming)AerodynamicsTemplate (C++)Conditional probabilityOperator (mathematics)CompilerType theoryInterface (computing)PolynomialMultiplication signMetaprogrammierung2 (number)Type theoryData structureInheritance (object-oriented programming)Condition numberMetreComputer animation
17:23
CoefficientDifferent (Kate Ryan album)Ring (mathematics)Inheritance (object-oriented programming)AerodynamicsTemplate (C++)Conditional probabilityCompilerType theoryOperator (mathematics)PolynomialInterface (computing)CASE <Informatik>Social classMachine visionRange (statistics)Entire functionFrame problemView (database)Operator (mathematics)PolygonFrictionRing (mathematics)Euklidischer RingMereologyType theoryParameter (computer programming)Template (C++)Computer animation
18:04
PolynomialRing (mathematics)Time domainGreatest common divisorSoftware testingCoefficientDifferent (Kate Ryan album)ChainConditional probabilityHierarchyInterface (computing)Social classINTEGRALInterface (computing)PolynomringType theorySoftware testingCondition numberHierarchyEntire functionAbstractionCASE <Informatik>Social classRing (mathematics)Operator (mathematics)Right angleMultiplication signBit rateComputer animation
18:55
Social classHierarchyAlgebraic numberTemplate (C++)AbstractionDirected setType theoryInterface (computing)Data conversionInheritance (object-oriented programming)Conditional probabilityPolynomialAdaptive behaviorSeries (mathematics)Interface (computing)Field (computer science)Type theoryTypsichere SpracheHierarchyAlgebraic structureAdaptive behaviorMultiplication signUsabilityObject-oriented programmingMultivariate AnalysePrime idealField (computer science)CoefficientPolynomialTemplate (C++)Social classCodeSymbolic computationInterface (computing)Power seriesSeries (mathematics)Computer animation
19:43
EmailEmailComputer animation
Transcript: English(auto-generated)
00:01
Welcome, everyone. Today, we are going to discuss the use of C++ templates in the design of a computer algebra library, in particular, BPAS. I would like to thank my co-authors Robert Moir, Marc-Mano Mazza, while myself, Alex, will be giving the talk today. So what is the BPAS library? The Basic Polynomial Algebra Subprograms Library,
00:22
BPAS, is a computer algebra library for high-performance polynomial algebra. Its name is Arifon-Blas and has a similar motive to enable efficiency in its users by providing the building blocks of polynomial algebra. This efficiency is enabled through both high-performance code and an easy-to-use interface.
00:41
Its high performance is thanks to a core implementation of optimized C code. This code is high-performing thanks to a very careful implementation, which considers data locality, cache complexity, and parallelism. It's implemented specifically with modern architectures in mind, and so is concerned with the memory hierarchy, multi-core, and multi-processors.
01:02
This core implementation is wrapped in a very lightweight interface written in C++. This interface, which is the topic of today's talk, makes the library easy to use through a natural object-oriented paradigm. This interface is so-called dynamic thanks to the use of templates and template metaprogramming, as we'll see throughout the talk.
01:23
Moreover, it's important to note that this lightweight wrapper does not really introduce overhead since all of the actual computation occurs in the underlying C code. So what functionality is available under this interface? Several years ago now, in ICMS 2014, we presented our FFTs,
01:40
parallelized polynomial arithmetic, and real root isolation. More recently, we worked on very large FFTs, FFTs over a prime field with very large characteristic, as well as a thorough treatment of sparse multivariate polynomials. These operations underlie a parallelized implementation
02:02
of triangular decomposition via regular chains. That is, to solve systems of polynomial equations using triangular decomposition. So let's see the plan for this talk. I'll begin by discussing the motivation behind our design, then a little bit of background on templates.
02:21
What remains is there are two main topics. First, the encoding of the algebraic hierarchy as a class hierarchy, and second, augmenting that hierarchy to include polynomials. This is the so-called dynamic part of the hierarchy, as we'll see. The biggest motivation in our interface design is usability.
02:41
We want to make BPAS simple and easy to use. Accessibility and interoperability is achieved through our choice of implementation language, which is C and C++. Usability, on the other hand, means a lot of things. In our particular context, we're concerned with five things toward that end. First is that the interface must be natural
03:01
to use for an end user. In particular, a end user mathematician might expect a natural and symmetric encoding of the algebraic hierarchy. Second, that encoding should be easy to use. Therefore, the algebraic hierarchy should be encoded as a class hierarchy, since object-oriented design is so ubiquitous now.
03:22
Such an algebraic class hierarchy would be easy and intuitive to use for most users. This class hierarchy allows for rings to be encoded as classes. Meanwhile, elements of a ring are objects of that class. Third, this interface should follow encapsulation.
03:42
Since the core of the library is highly optimized C code, it's also relatively complex. Therefore, a wrapper interface would encapsulate all of these complexities and provide a clean interface to the user. Fourth, this interface should be extensible to include and handle user-defined types.
04:01
Object-oriented design naturally allows for this. Finally, fifth, a very important aspect is type safety. We want this interface to be both type safe in the programming language sense, but also mathematically type safe. And in particular, all of this should occur at compile time.
04:22
What do we mean by mathematical type safety? We mean compatibility between different rings. So throughout the talk, let's consider rings as commutative and with unity. Then an example best illustrates what we mean by mathematical type safety. If you consider the integers module of 17
04:42
and univariate polynomials over the rational numbers, both are Euclidean domains. In a direct encoding of the algebraic hierarchy as a class hierarchy, we see that both of these algebraic structures have Euclid domain as their superclass. They are both Euclidean domains. However, via polymorphism,
05:02
these classes are compatible in the sense of the programming language. For example, here in this code segment, where we get the remainder between a rational polynomial and an integer module of 17, it's completely compile-time valid code. But runtime errors would be expected
05:22
since these rings are in fact mathematically compatible. Before looking at our particular solution to this problem, let's see what exists in other compiled libraries. As a first example, you can consider Singular's polynomial library.
05:41
There, all coefficient rings of a polynomial are encoded by a single class. Then this one class has many instance variables taking Boolean and enumeration values to encode information about which particular ring an instance of this class is. In COCO, a ring and its subclasses,
06:02
Euclidean domain, integral domain, are all one class hierarchy. However, elements of a ring are encoded as a separate class. Then for mathematical type safety, it's only ever a runtime property. In fact, ring elements hold references
06:22
to their so-called owning ring, and these references are compared at runtime. If the references don't match, a runtime error occurs. This story is similar in Linbox, where separate classes encode rings and elements of a ring. However, instead of comparing references there,
06:42
they instead use downcasting, where a reference to an abstract ring element object is downcasted to a particular ring object. Of course, downcasting goes against principles of object-oriented and polymorphic design, and so should be avoided.
07:02
So our goal is to achieve this mathematical type safety at compile time rather than at runtime using value checks. We want to make it hard to do the wrong thing. Thus, we have to catch such issues at compile time and prevent the code from being executed in the first place.
07:21
This is achieved through a class template hierarchy for the algebraic hierarchy. So speaking about templates, let's begin with a quick refresher on what templates are in C++ and some associated concepts. A class template is simply a class definition which is parameterized by some other type or class.
07:42
This parameter can be used throughout the class definition as if it were a real type, and then at compile time, when the parameter is given a particular value, cogeneration occurs for so-called template instantiation. What's nice about this is that the cogeneration and the resulting function overload resolution
08:03
occurs completely at compile time. This is an important concept for template metaprogramming. This metaprogramming is the use of templates to control and modify a program's code itself during the compilation process. It's much like macros and using the preprocessor,
08:21
but much more powerful. And this power comes from the fact that using templates, we can get compile time code evaluation. For example, you can use introspection via compile time code evaluation. So what compile time introspection is about
08:43
is determining properties of the type at compile time. Since template instantiation occurs at compile time, the resulting function overload resolution occurs at compile time, and therefore introspection is possible. Let's consider a simple example to show this point.
09:02
We have a type foo, which has some other type x defined inside of it. We then have two test functions. So they're overloaded. The first test function accesses type x within the namespace of its template parameter t, and it returns a type char.
09:22
The second test function takes any parameter and returns an integer. Then with the little macro, introspection can be done to determine at compile time whether a type has another type x defined in it. When the macro type has x is past the type foo,
09:43
the first test function is chosen during a function resolution, which returns a char. Charrs have size one, and therefore the macro evaluates to true for the type foo. On the other hand, the type int does not have a type x, and thus during function resolution,
10:03
the second test function is chosen, which returns an int. Ints have size at least two, and thus the macro evaluates to false. So we see that introspection on types is possible. And in general, there's many introspective possibilities, as we'll see.
10:22
So now let's consider these template techniques in our algebraic hierarchy. Our solution is to use an algebraic class template hierarchy. The abstract classes provide well-defined interfaces, which can be built up incrementally using inheritance. The abstract classes themselves provide the possibility
10:43
for default behavior and default function definitions. We use the template parameter to define the type, which should be used as parameters and return types in the interface itself. For example, we see that the Euclidean domain class provides a remainder method. However, the template parameter chooses
11:02
the method's parameter and return types. Thus, the method declaration itself stops dynamic polymorphism from causing mathematical incompatibility at runtime. Let's see how this works with an example. The key is that the parameter is specialized to a particular concrete type.
11:22
For example, when defining the ring of integers, we fit it into the algebraic hierarchy as the Euclidean domain by inheriting from the class Euclid domain. Simultaneously, the Euclid domain template parameter is instantiated as the subclass integer itself. This may seem weird,
11:41
but it's a totally valid C++ technique called the Curiously Recurring Template Pattern, or CRTP for short. What is nice about this technique is that it allows for the interface of integer, which is inherited from Euclid domain, to actually be precisely defined for the integers itself, and only the integers.
12:01
Notice that by this template instantiation, the remainder method of the class of integers is defined to return an integer and take an integer as a parameter. Symmetrically, the class of rational polynomials, which again use CRTP with Euclid domain superclass, has a remainder function, or remainder method also.
12:22
This time, however, by template instantiation, the parameter and return types of the remainder method are rational poly. Hence, at compile time, incompatibility is found immediately, since the function declaration itself stops incompatibility via compiler errors. For example, when we try to get the remainder
12:41
of a rational polynomial by an integer, a compiler error occurs because, well, an integer is not a rational poly. The method declaration itself stops any incompatibility from happening. However, one might say that technically it is valid to take the remainder of a rational polynomial
13:01
by an integer, since there exists a natural ring embedding from the integers to the rational polynomials through the rational numbers. This is true, and thus we would like to have a mechanism to allow such natural embeddings. Our solution is to use implicit conversion of C++ to do all the work for us.
13:21
By explicitly defining a constructor in the rational poly class, which takes an integer as a parameter, the compiler is able to perform implicit conversion from integers to rational polynomials. Therefore, this framework can be seen as explicitly giving permission for compatibility between rings by defining such a constructor. This is counter to existing solutions
13:41
which work restrictively, essentially allowing everything at compile time, and then only catching incompatibility at runtime. Our solution is permission-based rather than restriction-based. Finally, we look to augment our algebraic class hierarchy with polynomials. For the purpose of code reuse, maintainability,
14:02
logical simplicity, we would like our abstract polynomial classes to be templated by their coefficient ring. This can be done by simply adding a second template parameter. Here you see that the poly class has two template parameters, the coefficient ring and the derived parameter, which is used for CRTP, as we just saw.
14:22
Then we have the concrete rational poly class. It provides rational number as the coefficient ring, and then itself as the CRTP template parameter. However, two problems exist with the simple definition. First, what if the co-if ring, the template parameter, is not actually a ring?
14:41
For example, if it was the strings or some user-defined type like Apple, right? We want it to make it hard to do the wrong thing. The second problem is that this solution does not adapt to the idea that a particular polynomial ring
15:02
is a particular algebraic type depending on the type of its coefficient ring. So considering univariate polynomials as we move forward, you could always work recursively for multivariate polynomials. We see that the polynomials over the rationals form a Euclidean domain,
15:21
but polynomials over the integral domain, sorry, over the integers form only a integral domain. So this is a problem we want to tackle as well. For the first problem, we employ our first metaprogramming technique. The derived from struct has two template parameters, T and base. When specialized, if T is not a subclass of base,
15:43
a compiler error occurs. Otherwise, it continues happily. To use this struct, the polyclass simply inherits from derived from, passing its own coefficient ring, a template parameter, to derived from as the T parameter. The base parameter is statically defined
16:01
as the topmost class of our algebraic class hierarchy, ring. Using this technique provides a clean way of terminating compilation if a polynomial's coefficient ring is not a true ring. This allows developers to assume that the COEF ring template parameter at least adheres to the topmost ring's interface,
16:24
making implementation much easier. As for the second problem, we need to make further use of metaprogramming to adapt and be dynamic to changing coefficient rings. This is achieved through so-called conditional inheritance.
16:41
This technique begins by determining the type of a coefficient ring using introspection. The is base of structure is much like derived from. It takes an apparent subclass T and a superclass base. If T is a subclass of base, it evaluates to true. Otherwise, it evaluates to false.
17:00
Using templates, all of this evaluation occurs at compile time as well. The second metaprogramming structure is conditional. It essentially implements the tertiary conditional statement but for types. And in particular, it evaluates this condition at compile time. So combining this with is base of
17:22
naturally yields conditional inheritance. Consider a first example of the poly class. There's a lot of syntax, but we can break it down into three parts. First, is base of determines if the C ring, the COF ring template parameter is a field.
17:41
If it is, then conditional chooses Euclidean domain as the type of this polynomial via the superclass. Otherwise, it chooses just generic ring. So in this way, the poly class can dynamically determine if it's Euclidean domain or just a normal ring.
18:05
But we want even more flexibility than this. We want an entire case discussion to determine precisely what is the algebraic type of a polynomial based on its coefficient ring. So our solution has two parallel hierarchies.
18:20
On the left, we have the true abstract class hierarchy, which builds up the interface incrementally. And on the right, we have the so-called tester hierarchy, which has a cascade of conditional and is base of checks to determine the true algebraic type of a coefficient ring
18:40
and thus the polynomial ring. Then concrete classes inherit from this bottom right polynomial class to automatically determine their type and thus their interface at compile time. So finally, we have seen the interesting aspects of our algebraic class hierarchy.
19:00
It is an algebraic class hierarchy, which makes use of object-oriented techniques to create a natural and symmetric encoding of the algebraic hierarchy. Via templates and template metaprogramming, this class hierarchy is mathematically type safe at compile time, as well as dynamic and adaptable to polynomials of various coefficient types.
19:21
In future, we look to further extend this hierarchy to include more interesting algebraic structures like multivariate power series and polynomials over prime fields. Moreover, for even greater usability and widespread adapting of BPAS, we want to create another wrapper, this time in Python, on top of our C++ interface.
19:43
So thank you for watching and attending this talk. Questions and comments can be made later during the live Q&A session or via email at any time. Thanks again for watching.
Recommendations
Series of 8 media