BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Yacine Bouzidi

Yacine Bouzidi contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometrySymbolic Computation

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

preprint2014arXiv

Improved algorithm for computing separating linear forms for bivariate systems

We address the problem of computing a linear separating form of a system of two bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and this is the bottleneck of these algorithms in terms of worst-case bit complexity. We present for this problem a new algorithm of worst-case bit complexity $\sOB(d^7+d^6τ)$ where $d$ and $τ$ denote respectively the maximum degree and bitsize of the input (and where $\sO$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity). This algorithm simplifies and decreases by a factor $d$ the worst-case bit complexity presented for this problem by Bouzidi et al. \cite{bouzidiJSC2014a}. This algorithm also yields, for this problem, a probabilistic Las-Vegas algorithm of expected bit complexity $\sOB(d^5+d^4τ)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Separating linear forms for bivariate systems

We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity. Given two bivariate polynomials of total degree at most $d$ with integer coefficients of bitsize at most~$τ$, our algorithm computes a separating linear form in $\sOB(d^{8}+d^7τ)$ bit operations in the worst case, where the previously known best bit complexity for this problem was $\sOB(d^{10}+d^9τ)$ (where $\sO$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Rational Univariate Representations of Bivariate Systems and Applications

We address the problem of solving systems of two bivariate polynomials of total degree at most $d$ with integer coefficients of maximum bitsize $τ$. It is known that a linear separating form, that is a linear combination of the variables that takes different values at distinct solutions of the system, can be computed in $\sOB(d^{8}+d^7τ)$ bit operations (where $O_B$ refers to bit complexities and $\sO$ to complexities where polylogarithmic factors are omitted) and we focus here on the computation of a Rational Univariate Representation (RUR) given a linear separating form. We present an algorithm for computing a RUR with worst-case bit complexity in $\sOB(d^7+d^6τ)$ and bound the bitsize of its coefficients by $\sO(d^2+dτ)$. We show in addition that isolating boxes of the solutions of the system can be computed from the RUR with $\sOB(d^{8}+d^7τ)$ bit operations. Finally, we show how a RUR can be used to evaluate the sign of a bivariate polynomial (of degree at most $d$ and bitsize at most $τ$) at one real solution of the system in $\sOB(d^{8}+d^7τ)$ bit operations and at all the $Θ(d^2)$ {real} solutions in only $O(d)$ times that for one solution.

0 citations0 reviewsNo code linkedOpen access