Ask Your Question
1

Cylindrical Algebraic Decomposition and connected components

asked 2022-11-13 23:26:21 +0100

kevinfat gravatar image

updated 2024-04-19 21:26:19 +0100

FrédéricC gravatar image

From what I've read Sage has support for accessing QEPCAD which implements Cylindrical Algebraic Decomposition.

Given a collection of polynomial inequalities I would like to know if they define a single connected region or multiple regions. It looks to me that the Cylindrical Algebraic Decomposition can be used to determine that though I don't know how to get at that. Does QEPCAD support that question or do I need to understand a lot of details to implement that using QEPCAD?

edit retag flag offensive close merge delete

Comments

From reading documentation at https://doc.sagemath.org/html/en/refe... the answer appears to be Yes. Just count how many cells have required polynomial signs and check if this number is 1.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-11-14 06:12:57 +0100 )edit

I don't think cells represent largest connected regions.

kevinfat gravatar imagekevinfat ( 2022-11-15 04:12:41 +0100 )edit

Why? When we cross a boundary between two cells, the inequality corresponding to this boundary changes its sign. Hence, if there is a path connecting two points and preserving all inequalities along the way, it should not cross any cell boundaries, meaning that such a path must be entirely within a single cell.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-11-15 15:18:24 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2023-01-08 21:40:50 +0100

kevinfat gravatar image

So I figured out how to compile sage from source with qepcad. There is already a connectivity test in qepcad. For example the following works.

var('a')
qf = qepcad_formula
qepcad(qf.connected_subset(a, a^2 - 1 > 0))
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-11-13 23:26:21 +0100

Seen: 372 times

Last updated: Jan 08 '23